[Bug 275661] /usr/bin/dc really slow with a trivial calculation

From: <bugzilla-noreply_at_freebsd.org>
Date: Tue, 26 Nov 2024 21:12:33 UTC
https://bugs.freebsd.org/bugzilla/show_bug.cgi?id=275661

--- Comment #5 from Stefan Eßer <se@FreeBSD.org> ---
(In reply to Stefan Eßer from comment #4)
I have had some time to think about this issue, and improvements should be
possible for some cases without loss of precision of the results.

Error propagation allows to calculate the required number of digits in the
fractional part of intermediate results.

The following cases have to be distinguished:
 * base > 1 and positive exponent
 * base < 1 and positive exponent
 * base > 1 and negative exponent
 * base < 1 and negative exponent

A base value < 1 with negative exponent requires very high precision of
intermediate results:

Consider a base value of 0.1 and a negative exponent "n", which should return
10^n for any scale >= 1 (i.e. at least 1 fractional digit). This requires
intermediate results to be calculated with n fractional digits (e.g.: 0.1^-4 =
1/(0.1 ^4) = 1/0.0001 = 10^4).

A possible optimization is to normalize the base value to have a leading digit
of 1..9 (i.e. multiply by a suitable power of 10; divide the result by that
multiplicator^n to get the result using only the required precision of the
result; multiplication by powers of 10 is a very efficient operation in this
bc/dc implementation).

The current implementation uses intermediate scale values (precision of the
fractional part) that are proportional to the exponent, but this is not
actually required for an exact result, if the above mentioned normalization of
the base value is applied. For the test cases with scale=16 and
1.0000001^(2^27) the intermediate results will have 16*2^27 fractional digits
...

I'll calculate the error propagation for the cases of positive and for negative
exponents (assuming a base value >= 1 after applying the above mentioned
normalization).

-- 
You are receiving this mail because:
You are the assignee for the bug.