stillwater-sc / universal / 31918528977

85%

master: 84%

Build Type

push

github

Committed by web-flow

Commit Message

fix(qd_cascade): compress the expansion before renormalizing addition (#1321)

qd_cascade sqrt/exp/log delivered 48-50 correct decimal digits where the format
carries 63.6 and classic qd delivers all of them. The cause was in none of those
functions.

expansion_ops::add_cascades() returned a sum whose value was exact but whose
components overlapped - consecutive terms within a factor of two of each other
rather than 2^53. compress_8to4() is QD's renorm, built from fast_two_sum chains
that are only error-free when |a| >= |b|; handed an overlapping expansion it ran
out of places for the tail and returned a result whose fourth component was
exactly zero. A relative error of 2^-160 in a format carrying 2^-212, on roughly
one addition in eight, inherited by everything built on addition.

Fixed with expansion_ops::compress_expansion<M>(), Shewchuk's COMPRESS
(Geometric Predicates, Fig. 22), applied to the floatcascade<4> overload only;
the <2> and <3> overloads were measured over 5000 random full-precision
additions each and stay within 0.49 ulp with or without it.

Verified against an exact decimal oracle sharing no code with the library:
exp and log now match qd to the last bit, sqrt goes from 48.9 to 63.2 digits.

Cost: quad-double addition is 46% more expensive, which reverses one of the
#1315 benchmark conclusions - qd_cascade's dot product measured 0.83x qd only
because the addition was dropping a component; it is 1.15x with the correct
addition. The benchmark README is re-measured accordingly.

New tests validate addition against exact dyadic-rational arithmetic
(dyadic_exact.hpp): 825 of 4096 cases fail at REGRESSION_LEVEL_4 on the old
code, all pass on the new.

Closes #1317. Follow-up on multiplication: #1322.

Coverage Stats

27 of 27 new or added lines in 1 file covered. (100.0%)

39 existing lines in 4 files now uncovered.

42588 of 49820 relevant lines covered (85.48%)

7285597.94 hits per line