Kahan compensated summation

Adding a long list of numbers seems like the safest thing in the world, yet it is a classic way to bleed accuracy. Each time you add a new term to a large running total, the small low-order bits of that addition are rounded off and thrown away; over a million additions those discarded crumbs pile up into a real error. Kahan compensated summation, named after William Kahan, is a clever fix that catches the crumbs and feeds them back in.

The idea is to keep a second variable, c, that remembers the rounding error lost on the previous step, and to add it back before the next term. The loop reads: for each x, set y = x - c (correct this term by the running compensation); set t = sum + y (the rounded new total); set c = (t - sum) - y (recover exactly how much of y was lost to rounding); then set sum = t. The subtraction (t - sum) - y is exact and isolates the discarded low-order bits, which c carries forward into the next addition. It costs three extra cheap operations per term and no extra memory to speak of.

The payoff is dramatic: naive sequential summation of n terms has a worst-case relative error growing like n*u, while Kahan summation's error is bounded by roughly 2u plus a tiny term independent of n — essentially as if you had summed in much higher precision. It is the standard tool whenever you sum many values of similar sign and magnitude (means, dot products, numerical integration, physics time-steps). Two honest caveats: an aggressively optimizing compiler can 'simplify' c to zero by assuming real-number algebra, so the trick may need protection (volatile, or a no-fast-math flag); and pairwise summation, which recursively splits the sum, achieves a similar O(log n)*u bound more cheaply and is what many libraries actually use.