stillwater-sc / universal / 32589765478

85%

master: 84%

Build Type

push

github

Committed by web-flow

Commit Message

perf(elreal): make division by a single block linear instead of quadratic (#1377)

* perf(elreal): make division by a single block linear instead of quadratic

singleDiv followed FCL.hs literally: divide EACH dividend block independently to a
full stream, then infSum the D of them. That is correct but quadratic -- term i must
be carried down to the output frontier, so D quotient blocks cost D^2/2 block
divisions. Counted directly: 2*D^2 twoDivZBCL calls to produce D blocks.

Dividing an N-digit number by a ONE-digit divisor is a linear operation. What makes
the schoolbook carry work here is that the residual of f_i/g lands at the scale of
f_{i+1}, so the two add and a single running remainder suffices:

    rem  += next dividend block
    (s,e) = twoDiv(rem.head(), g)      -- one quotient block, exact residual
    rem   = rem.tail() + e             -- carry

Block divisions are now linear in the emitted blocks: 1.00 per block on a double
host, 1.06-1.09 on float, against the old D/2.

    D  |  before      after     speedup      before/after growth per 2x D
    20 |   14.1 ms    0.179 ms     79x
    40 |   53.3 ms    0.352 ms    151x       x3.77  /  x1.97
    80 |  265.2 ms    0.704 ms    377x       x4.97  /  x1.99
   160 | 1682.7 ms    1.423 ms   1183x       x6.34  /  x2.02

x2.02 per doubling is linear; the old x6.34 is not. On float the division count is
linear too but a larger running remainder leaves the wall clock at x3.2 per doubling,
so the gain there is 51x-358x rather than asymptotic. Worth revisiting separately.

Still a LAZY producer: one quotient block per pull, so an infinite quotient (1/3)
streams for as long as the caller asks. Verified to 400 blocks.

PENDING BUFFER. The raw quotient blocks are not always 0-overlap: on a double host
they arrive with gaps of k+1 and need nothing, but on float about 2 in 60 land one
bit too close. Renormalising the finished expansion would have been self-defeating --
priestRenorm over D blocks is itself... (continued)

Coverage Stats

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

18 existing lines in 2 files now uncovered.

43112 of 50496 relevant lines covered (85.38%)

7159736.45 hits per line