Kahan summation algorithm

Remarks

The variable $c$ holds the low-order part lost when $y$ is added to the large running sum $s$. The difference $t - s$ recovers what was actually added, and subtracting $y$ gives minus the round-off error of the addition. This correction is fed back into the next term. The proof tracks the rounding errors of the four operations through the loop; the key point is that, in binary arithmetic, $c$ captures the rounding error of $s + y$ almost exactly. For comparison, plain recursive summation only gives the bound $\frac{(n-1)u}{1 - (n-1)u} \sum \abs{x_i}$, which grows linearly in $n$. The result is a backward error bound: $\hat s$ is the exact sum of the slightly perturbed terms $(1 + \mu_i) x_i$. The relative error $\abs{\hat s - s}/\abs{s}$ can still be large when $\sum \abs{x_i} \gg \abs{\sum x_i}$, that is, when the sum is ill-conditioned. Optimizing compilers that treat floating-point addition as associative can simplify $c$ to $0$ and destroy the method.

Going deeper

For a student

The bound should be compared with the bound $\gamma_{n-1} \sum \abs{x_i}$, $\gamma_k = ku/(1 - ku)$, for recursive summation and $\gamma_{\lceil \log_2 n \rceil} \sum \abs{x_i}$ for pairwise summation. Compensated summation costs four floating-point operations per term instead of one, but removes the dependence on $n$ from the leading term. It is the simplest example of an error-free transformation: the pair $(t, -c)$ represents $s + y$ exactly or nearly exactly. The same idea underlies compensated algorithms for dot products and polynomial evaluation.