KAHAN SUMMATION carry the bits that fell off the edge back into the sum
Add a large running total to a small term and the small term’s low-order bits fall off the end of the float and are lost forever. Kahan summation keeps a separate compensation variable that captures exactly those lost bits and feeds them back into the next addition — so a sum that naive floating-point rounds to nothing is recovered to full precision. On an f64-only language it is the difference between a total and a lie.
THE TECHNIQUE track the lost part; feed it forward
Sum [1, 1e-16, 1e-16, -1]. Each 1e-16 is smaller than the last bit of 1.0, so naive addition drops both and the total collapses to 0. Kahan carries the dropped part in c and returns it. Watch the compensation catch the remainder: live demo
HISTORY & CREDIT William Kahan, CACM 1965
“Adding the same numbers always gives the same sum.” — no. Floating-point addition is not associative: the order and the running magnitude decide what is lost, so (big + tiny) + tiny can differ from the true total by the whole tail. Kahan does not change the numbers, only which bits survive. cited
1965 · William Kahan — “Further remarks on reducing truncation errors” (CACM 8(1)): the compensated-summation algorithm. 1969 · Ivo Babuška — independently gives a compensated sum; the technique is sometimes co-credited. 1974 · Arnold Neumaier — an improved variant that also handles the case where the next term is larger than the running sum.
The one line that matters is c = (t - sum) - y: after t = sum + y rounds, (t - sum) is the part that survived, so subtracting y leaves exactly the part that was lost — the remainder, kept. Kahan, 1965
RECOMMEND FOR I-13 the remainder, recovered
On the canonical f64 compiler, naive summation loses the small terms entirely and Kahan recovers them:
$ i13 run kahan.i13 # sum [1, 1e-16, 1e-16, -1] (true ~ 2e-16)
ns = 0 -- naive: both 1e-16 fall off 1.0, then -1 -> 0
ks = 0.0000000000000002220446049250313 -- Kahan: the compensation carried the lost bits back
Recommend: Kahan summation is LIT and the most on-point numeric dart for I-13 — a language whose only number is the f64 float. Verified on the canonical compiler: naive summation of [1, 1e-16, 1e-16, -1] returns 0 (the small terms vanish), while Kahan returns 2.22e-16, the true tail recovered by the compensation term. It is four lines of pure f64 arithmetic (y=a-c; t=sum+y; c=(t-sum)-y; sum=t) — no new value kind, native recursion — and it belongs in any I-13 routine that sums many terms (an integral, a dot product, a mean). The deeper reason it belongs in this corpus: the bits that fall off the rounding seam are not noise to be dropped — they are an exact, computable quantity ((t−sum)−y), and Kahan carries them across the seam rather than losing them. That is the corpus’s own law of the honest crossing (THE TRANSCRIBER) and its .dlw nothing-lost ethos made arithmetic: naive reports 0, Kahan reports the recovered tail 2.22e-16 — the residue itself, not a rounding of it.