"how numbers are stored in computers"

Kahan Summation Formula

This theorem shows that the Kahan summation algorithm computes a sum with significantly less rounding error than naïve summation. Specifically, each term is distorted by at most a small relative error , with:

In naïve summation, small rounding errors pile up. Worst case, early terms like get multiplied by lots of small relative errors (like ), leading to distortion. Kahan summation tries to fix this by tracking the error introduced at each step, and subtracting it off in the next step.

For each term , it first corrects the term by subtracting the previously lost bits . It then performs the floating-point addition and updates the compensation term to store the newly lost bits (), therefore reclaiming lost precision bit by bit.

Even though each operation introduces rounding error, the algorithm systematically cancels much of it out. It turns out that the distortion for each term is only about , so the total error is quadratic in instead of linear — a huge improvement.

Kahan summation doesn't eliminate rounding error, but it controls it very effectively. Instead of errors accumulating linearly with the number of terms , they grow relative to , which is tiny in practice. This makes it a gold standard in high-accuracy numerical computing.

Theorem

Suppose a sum is computed using the following algorithm:

Then the computed sum satisfies:

Proof

In naive summation, define:

Then the computed sum is:

This leads to large coefficients of rounding error on early terms (e.g. ). Let:

Here, are small error terms .

First Iteration (k = 1)

We compute:

Call the coefficients of in these expressions and .

Recurrence Relations

By ignoring higher-order terms (i.e., ):

From these, it can be shown:

Let , then:

So the coefficient of in is at most:

Hence, the total error is bounded by: