Summing floats without losing your mind

Add a million small doubles to a running total and the answer is wrong in the fourth or fifth significant digit. Not wildly wrong, just wrong enough that two implementations of the same metric disagree and someone opens a ticket.

Why it drifts

A double has about 16 decimal digits. Once the running sum is large, each small addend loses its low bits when it is aligned to the sum's exponent. The lost bits are not random, they are biased in the direction of whatever rounding mode is active, so the errors accumulate instead of cancelling.

Kahan

Keep a second variable that tracks the rounding error from the previous step and feed it back in. Four floating point operations per addend instead of one.

sum, c := 0.0, 0.0
for _, x := range xs {
    y := x - c
    t := sum + y
    c = (t - sum) - y
    sum = t
}

The error is now bounded by a small constant times machine epsilon, independent of how many terms you add. The compiler must not reassociate these operations, so check that fast-math is off for this function.

Pairwise

If the data is already in memory, sum halves recursively and combine. Error grows with the logarithm of the count instead of linearly, and it vectorises, which Kahan does not. For a streaming sum Kahan wins; for a batch reduction over an array, pairwise is usually faster and good enough.

Numbers

Summing ten million values of 0.1: naive gives 999999.9998389754, Kahan gives 1000000.0000000000, pairwise gives 1000000.0000000002. The naive answer is off by about one part in ten million, which is exactly the kind of discrepancy that survives code review and dies in production.