stillwater-sc / universal / 31947713322

85%

master: 84%

Build Type

push

github

Committed by web-flow

Commit Message

fix(qd_cascade): replace the sorted multiply with the qd_mul schedule (#1323)

qd_cascade multiplication was ~2 decimal digits behind qd on full-width
operands (1.7e-63 vs 1.6e-65 worst case) and 8x slower. Both came from the
same decision: the old implementation sorted a 32-term expansion (up to 496
compare-and-swap steps) and folded it into 4 components with a carry loop
that discarded the error term of every sub-ulp carry.

multiply_cascades(floatcascade<4>, floatcascade<4>) is now a transliteration
of the classic qd_mul, which needs no sorting at all: a[i]*b[j] contributes at
order eps^(i+j), so products come out in decreasing significance by
construction. renorm5() closes the five-term accumulation.

Two smaller pieces came with it: multiply_cascade_by_double(), without which
fixing multiplication would have made division 23% SLOWER (the initial
quotient estimate is a one-component cascade); and a non-finite guard, since
two_prod(inf, x) is NaN and the old multiply turned inf * 3 into a NaN.

Multiplication now matches qd bit for bit against an exact decimal oracle,
worst and median. Measured: multiply 581 -> 82 nsec/op, exp 26036 -> 6642,
log 75321 -> 21814, sqrt residual 15 -> 8.6 ulps.

Closes #1322.

Coverage Stats

130 of 131 new or added lines in 1 file covered. (99.24%)

29 existing lines in 3 files now uncovered.

42666 of 49920 relevant lines covered (85.47%)

7253758.44 hits per line