THE FOLD / GRIND / THE-GRINDSTONE / THE TWO-SUM
THE TWO-SUM
the rounding error captured exactly
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Two-Sum is a tiny miracle of floating-point arithmetic: it adds two numbers and hands you the rounding error, exactly. Ordinary a + b rounds to the nearest representable value s, silently discarding a little bit e. Two-Sum computes both, so that a + b = s + e is an exact equation over the reals — using only a handful of ordinary additions and subtractions, no wider precision. This “error-free transformation” is the seed of compensated summation, double-double arithmetic, and reproducible numerics.
LIT verified live: over 20,000 random pairs, s is exactly the rounded sum and the pair (s, e) reconstructs a + b exactly — checked by comparing exact dyadic fractions of the doubles (window.__two_sum). FIG no framing; Two-Sum and an exact BigInt comparison run in-browser.
LIT verified live: over 20,000 random pairs, s is exactly the rounded sum and the pair (s, e) reconstructs a + b exactly — checked by comparing exact dyadic fractions of the doubles (window.__two_sum). FIG no framing; Two-Sum and an exact BigInt comparison run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-grindstone — grind a long sum and the errors accumulate; Two-Sum catches each grain of error as it falls. AVAN (AI) built the instrument: Knuth’s Two-Sum, and an exact rational (dyadic BigInt) comparison to prove a + b = s + e.
Credit as content: Donald Knuth (Two-Sum); Dekker (the related fast version). The weave: David names the grindstone; I confirm the error term e makes a + b = s + e an exact identity, verified in exact arithmetic.
Credit as content: Donald Knuth (Two-Sum); Dekker (the related fast version). The weave: David names the grindstone; I confirm the error term e makes a + b = s + e an exact identity, verified in exact arithmetic.
3 ONE DIMENSION
a + b rounds to s and loses e; Two-Sum returns both, so s (the high part) plus e (the lost error) equals a + b exactly.
4 TWO DIMENSIONS · INTERACTIVE
Pick two numbers of very different scale; the naive sum drops bits, but Two-Sum’s (s, e) reconstructs a + b exactly.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the exact pair (s, e) representing a + b.
AVAN’s addition (the inverse-companion): don’t discard the rounding error — compute it. The inverse of ‘s = fl(a+b), lose the rest’ is ‘e = the exact error, so a + b = s + e with no wider precision.’ Magenta is the rounding error e a naive add throws away; green is the exact pair that keeps it. Capture the error.
LIT Genuine Two-Sum error-free transformation (Donald Knuth; Dekker's related fast version). Verified live: over 20,000 random pairs, s equals the rounded sum a+b and the pair (s,e) satisfies a+b=s+e exactly — confirmed by exact dyadic-fraction (BigInt) comparison of the IEEE-754 doubles (window.__two_sum.exact, .sIsRound).
FIG No framing: Two-Sum and the exact BigInt comparison run in-browser. The AVAN inverse is honest — instead of discarding the rounding error, one computes it: e is the exact error, so a+b=s+e holds with no wider precision. Magenta is the rounding error e a naive add throws away; green is the exact pair (s,e) that keeps it. Capture the error.
FIG No framing: Two-Sum and the exact BigInt comparison run in-browser. The AVAN inverse is honest — instead of discarding the rounding error, one computes it: e is the exact error, so a+b=s+e holds with no wider precision. Magenta is the rounding error e a naive add throws away; green is the exact pair (s,e) that keeps it. Capture the error.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE-GRINDSTONE · David Lee Wise (ROOT0), with AVAN