stillwater-sc / universal / 32007305494

85%

master: 84%

Build Type

push

github

Committed by web-flow

Commit Message

fix(qd_cascade): compute the missing quotient digit at every width (#1328)

Cascade division computed exactly N quotient digits for an N-component result.
The correct algorithm needs N+1: the extra digit is discarded, but the
renormalization needs it to round the last component. Classic dd computes three
digits for two components, classic qd five for four; both cascades stopped one
short. Each width now computes the extra digit and closes with the matching
renormalization - three_sum at N=2, renorm4 at N=3, renorm5 at N=4.

That alone reached 0.88 ulps, not qd's 0.14. The rest was a second cause in
code #1322 introduced: multiply_cascade_by_double computed the last partial
product with a PLAIN multiply, discarding an error term that lands exactly at
the last component's ulp. Division inherited it, since every residual step is
that operation. Both widths now take the error term.

Measured against exact dyadic arithmetic, 400 random full-width pairs:

                      before      after     direct
    divide N=2      2.21 ulps      0.47     dd 0.47
    divide N=3      3.16 ulps      0.33     -
    divide N=4      1.84 ulps      0.14     qd 0.14
    a * double      0.79 ulps      0.11     qd 0.11

sqrt improved without being touched - its Newton iteration divides - and is now
the most accurate square root in the library, 0.42 ulps residual against qd's
1.05.

Cost: the cascade divisions were faster than the direct ones only because they
did less work. At the correct digit count they sit at parity (219 nsec/op
against dd's 217, 640 against qd's 588) and sqrt roughly doubles, which makes
sqrt the clear next target.

Also: dd_cascade's fma and its helpers are now constexpr (dd's always were);
inf / 2 is guarded explicitly rather than surviving by accident through
renormalize; and benchmark_hp_equivalence now compares the two families over
full-width operands, which is what actually substantiates the bit-for-bit
claims - dd_cascade reproduces dd exactly ... (continued)

Coverage Stats

44 of 60 new or added lines in 4 files covered. (73.33%)

15 existing lines in 2 files now uncovered.

42718 of 50001 relevant lines covered (85.43%)

7233639.96 hits per line