stillwater-sc / universal / 32047357757

85%

master: 84%

Build Type

push

github

Committed by web-flow

Commit Message

fix(qd_cascade): three selectable square roots, defaulting to the most accurate (#1333)

All three cascade types iterated x' = (x + a/x)/2, one DIVISION per step.
That was reasonable when written, because cascade division was the cheap
operation - it computed one quotient digit too few. #1326 made division
correct and therefore expensive, and sqrt paid that fix once per iteration:
13.8x dd at N=2, 2.7x qd at N=4, the worst ratios in the suite.

Switching to a multiplication-only formulation turned out to be a trade rather
than an upgrade, so all three formulations are kept side by side behind
UNIVERSAL_{DD,TD,QD}_CASCADE_SQRT_ALGORITHM, defaulting to the most accurate
at each width:

    dd_cascade   NEWTON_DIVISION     1.4 ulps    607 ns   default
                 NEWTON_RECIPROCAL   1.9         358
                 KARP                5.5          78      = classic dd
    td_cascade   NEWTON_RECIPROCAL  0.51         619      default (faster AND
                 NEWTON_DIVISION    0.55         883       more accurate here)
    qd_cascade   NEWTON_DIVISION    0.26        2843      default
                 NEWTON_RECIPROCAL  0.66        1412      = classic qd

Karp doubles a double seed once, reaching 106 bits and no further, which is
why it exists at N=2 and cannot serve the wider types.

Stated plainly: with accuracy-first defaults, sqrt performance barely moves.
dd_cascade and qd_cascade keep the division iteration and stay at 14.4x dd and
2.8x qd; the speedups are one define away and each lands on its direct
counterpart's accuracy, but they are not what you get by default.

What the change delivers unconditionally:

  td_cascade improved outright, 957 -> 691 nsec/op and 1.10 -> 0.72 ulps.

  Every formulation scales the argument into [0.5, 2) by an exact power of two
  first, which fixes sqrt(maxpos) at all three cascade widths - it returns inf
  or NaN today in dd, dd_cascade and qd (#1332).

  The three formulations are documented against each ot... (continued)

Coverage Stats

33 of 39 new or added lines in 3 files covered. (84.62%)

8 existing lines in 1 file now uncovered.

42735 of 50023 relevant lines covered (85.43%)

7230459.16 hits per line