stillwater-sc / universal / 32599692203

85%

master: 84%

Build Type

push

github

Committed by web-flow

Commit Message

feat(elreal): offer the faithful long division alongside the Newton reciprocal (#1380)

For a DENSE (multi-block, non-power-of-two) divisor, div_online has computed
a/b = a * (1/b) with a Newton-Raphson reciprocal since #1068 -- a deliberate
deviation from McCleeary 4.2.6, adopted because the dissertation's long division
cost-exploded before its fan-out was bounded. That follow-up ("restore a bounded
faithful long division") is now available, without changing the default.

    div_online(a, b, depth)                                    // Newton, unchanged
    div_online(a, b, depth, DenseDivision::FaithfulLongDivision)

divideHelper_bounded truncates each level's operands to the budget that can still
reach the output frontier. The contributions decay geometrically -- level L sits
about L*k bits down -- so a level only needs the precision that survives to the
frontier. The result is identical to the unbounded recursion: verified against it on
100 random dense divisors across both hosts, matching to the expansion's full
capacity at 4-6x less cost. A +2 block guard is enough; +0 loses a few digits, +4 and
+8 add nothing.

The two policies agree on VALUE. Reconstructing q*b against a, over 8 random dense
divisors per depth:

    depth            16     32     48     64
    Newton          263    528    793   1056  digits
    long division   264    529    795   1059

so this is not a fast-vs-accurate trade. Both scale linearly with depth and neither
caps, Newton's former ceiling having gone with #1373.

WHICH IS CHEAPER DEPENDS ON THE DIVISOR'S WIDTH, which I had wrong until I measured
it across two axes rather than one. Long division relative to Newton:

    at depth 24, varying the divisor
        divisor blocks    2      4      6     10     16     24
        long div vs N   3.8x   2.4x   1.9x   1.5x   1.2x   0.92x

    with a 6-block divisor, varying the depth
        depth            16     32     48     64
        long div vs N   1.5x   2.6x   3.2x   ... (continued)

Coverage Stats

20 of 26 new or added lines in 1 file covered. (76.92%)

18 existing lines in 2 files now uncovered.

43127 of 50517 relevant lines covered (85.37%)

7189011.45 hits per line