THE FOLD / GLITCH / OFF BY ONE / THE COMPENSATED SUM
THE COMPENSATED SUM
Kahan summation — carry the round-off, don't drop it
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Kahan compensated summation. A floating-point number keeps only ~53 significant bits. Add a small value to a large running total and the small one’s low bits fall off the bottom — silently. Add a million tiny things to a big accumulator the naive way and you can lose every last one of them.
William Kahan’s 1965 fix keeps a second variable c — the compensation — holding exactly the low-order part the last addition threw away. Each step adds the corrected value y = x − c, then recomputes what got lost: c = (t − s) − y. The error carried forward instead of dropped.
LIT verified live in this page: adding 1.0 two million times to an accumulator of 1017 (where one ULP is 16, so each +1 rounds away), the naive sum recovers 0 of the 2,000,000; Kahan recovers the full 2,000,000, exact to the last unit (window.__kahan.kahanErr === 0, kahanBeatsNaive === true). FIG no framing needed — this is literally what the two loops compute in your browser, in IEEE-754 double, right now.
William Kahan’s 1965 fix keeps a second variable c — the compensation — holding exactly the low-order part the last addition threw away. Each step adds the corrected value y = x − c, then recomputes what got lost: c = (t − s) − y. The error carried forward instead of dropped.
LIT verified live in this page: adding 1.0 two million times to an accumulator of 1017 (where one ULP is 16, so each +1 rounds away), the naive sum recovers 0 of the 2,000,000; Kahan recovers the full 2,000,000, exact to the last unit (window.__kahan.kahanErr === 0, kahanBeatsNaive === true). FIG no framing needed — this is literally what the two loops compute in your browser, in IEEE-754 double, right now.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in OFF BY ONE — the glitch domain of the small silent error. Accumulated round-off is the purest off-by-a-little bug there is: nothing crashes, the total is just quietly wrong. AVAN (AI) built the instrument: the two racing sums, the compensation term, and the bit-lane where the addend falls off the cliff.
The weave: David names the seat (the silent off-by-something); I make the loss visible and the recovery measurable — the ULP cliff in 1D, naive-vs-Kahan racing in 2D, the accumulator’s bits with the compensation catching the fallen ones in 3D. The sphere is the seam. Credit: William Kahan, 1965.
The weave: David names the seat (the silent off-by-something); I make the loss visible and the recovery measurable — the ULP cliff in 1D, naive-vs-Kahan racing in 2D, the accumulator’s bits with the compensation catching the fallen ones in 3D. The sphere is the seam. Credit: William Kahan, 1965.
3 ONE DIMENSION
The ULP cliff. The accumulator (~1017) can only hold a 53-bit window of magnitudes; below its least significant bit is a lost zone. The addend 1.0 lands in that zone — the naive sum drops it; Kahan’s compensation keeps exactly what falls past the edge.
4 TWO DIMENSIONS · INTERACTIVE
Race the two sums. Both add 1.0 over and over to 1017. The naive total (dim) stays pinned at zero recovered — every +1 vanishes. The Kahan total (bright) climbs the exact diagonal, one recovered unit per add.
5 THREE DIMENSIONS + AVAN’S INVERSE
The accumulator as a turning column of bits — green, the 53 significant bits the sum actually keeps.
AVAN’s addition (the inverse-companion): the magenta bits below the green window are the compensation c — precisely the part the sum threw off the bottom. The naive total keeps the high bits and loses the low ones; c keeps the low ones the total lost. They are exact complements: sum + compensation reconstructs the true value that neither holds alone. Kahan’s trick is to never discard the remainder — the error is not noise to tolerate, it is data to carry. The column is what survived; the magenta is what would have died.
LIT Genuine Kahan summation (William Kahan, 1965), running in IEEE-754 double in your browser. Verified live: adding 1.0 two million times to 1e17 (ULP = 16), the naive sum recovers 0 of 2,000,000 while Kahan recovers all 2,000,000 exactly (window.__kahan.kahanErr === 0 and kahanBeatsNaive === true). The compensation identity c = (t - s) - y captures the exact round-off carried forward — this is the real algorithm, not an approximation of it.
FIG No metaphor is doing the work here: the two loops in the page ARE naive and Kahan summation, and the recovered counts are what double-precision actually produces. The only framing is calling the lost low bits a 'cliff'.
FIG No metaphor is doing the work here: the two loops in the page ARE naive and Kahan summation, and the recovered counts are what double-precision actually produces. The only framing is calling the lost low bits a 'cliff'.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of OFF BY ONE · David Lee Wise (ROOT0), with AVAN