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

https://bugs.freebsd.org/bugzilla/show_bug.cgi?id=275661

Stefan Eßer <se@FreeBSD.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|New                         |Open

--- Comment #4 from Stefan Eßer <se@FreeBSD.org> ---
The reason for the long run-time is the precision of intermediate results,
which is doubled for each sqare that is computed. Only the final result is
truncated to the number of fractional digits given by "scale".

Seems that GNU bc and dc behave similarly, but takes at least 10 times as long.

TBH, I do not understand why this high precision is required during the
calculation. Limiting the scale of the intermediate results to four times that
of the final result does not appear to lead to different results, but takes
only milliseconds instead of hours for the 2^27 case:

diff --git a/contrib/bc/src/num.c b/contrib/bc/src/num.c
index 83f84edb91fc..3ca8569ac52e 100644
--- a/contrib/bc/src/num.c
+++ b/contrib/bc/src/num.c
@@ -2164,6 +2164,8 @@ bc_num_p(BcNum* a, BcNum* b, BcNum* restrict c, size_t
scale)
        for (powrdx = a->scale; !(exp & 1); exp >>= 1)
        {
                powrdx <<= 1;
+               if (powrdx > scale * 4)
+                       powrdx = scale * 4;
                assert(BC_NUM_RDX_VALID_NP(copy));
                bc_num_mul(&copy, &copy, &copy, powrdx);
        }
@@ -2186,6 +2188,8 @@ bc_num_p(BcNum* a, BcNum* b, BcNum* restrict c, size_t
scale)
                if (exp & 1)
                {
                        resrdx += powrdx;
+                       if (resrdx > scale * 4)
+                               resrdx = scale * 4;
                        assert(BC_NUM_RDX_VALID(c));
                        assert(BC_NUM_RDX_VALID_NP(copy));
                        bc_num_mul(c, &copy, c, resrdx);

$ echo "16k 1.0000001 2 27^ ^ pq" | time dc
674530.4707410845593826
        0,00 real         0,00 user         0,00 sys

$ echo "16k 1.0000001 2 32^ ^ pq" | time dc
33732640224394636565435618255869697073648757344072857017852662008141\
33288999890928354175057633500291961443834127786206338597551908514660\
039786068330051950098862770779120895429155957796324.3657731486704926
        0,00 real         0,00 user         0,00 sys

$ ./tn -f; echo "16k 1.0000001 2 32^ ^ pq" | dc; ./tn -f 
1732559461.212034429
33732640224394636565435618255869697073648757344072857017852662008141\
33288999890928354175057633500291961443834127786206338597551908514660\
039786068330051950098862770779120895429155957796324.3657731486704926
1732559461.213839029
$ echo "16k 1732559461.213839029 1732559461.212034429 - pq" | dc
.001804600

For comparison the results for 2^20 using GNU dc:

$ echo "16k 1.0000001 2 20^ ^ pq" | time /usr/local/bin/dc
1.1105524506031247
      160,81 real       160,80 user         0,01 sys

And with the unpatched FreeBSD dc:

$ echo "16k 1.0000001 2 20^ ^ pq" | time dc-unpatched
1.1105524506031247
       13,47 real        13,47 user         0,00 sys

The limit of 4 times "scale" was chosen just to test the assumption that the
excessive length of the intermediate results was the cause of the slow
calculation. I have not made any attempt to identify the minimal scale value
that guarantees correct results. While doubling the number of fractional digits
for each sqare operation preserves all fractional digits of each intermediate
result, I'm not convinced that there are pathological operands that actually
require that precision.

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