Compensated summation

Compensated summation retains a correction for low-order information lost to roundoff error in successive floating-point arithmetic additions. Kahan summation is a common implementation; it can substantially reduce accumulated error when many terms are added.

The Kahan summation algorithm computes a sum in floating-point arithmetic while carrying a correction for low-order information lost by successive additions. With accumulator $s$ and correction $c$ initially zero, process each input $x$ in this order:Every operation shown is rounded in the working floating-point representation. The new $c$ approximates the portion added too much or too little in the rounded $s+y$, so the next input subtracts it. For binary64 inputs $1,2^{-53},2^{-53}$ in that order, ordinary left-to-right summation loses both small increments, returning one; this algorithm recovers $1+2^{-52}$.

The correction substantially improves many long sums, but is not an exact summation method and does not remove ill-conditioning when large opposite-sign terms nearly cancel. Its operation order is essential: a compiler that rewrites $(t-s)-y$ as exact algebraic zero destroys the correction.^[ref]