Does Kahan summation require sorting?

No. It processes inputs in their supplied order.

Does it always return the exact sum?

No. It reduces important sources of rounding error but has limitations.

Does it need memory proportional to the number of inputs?

The basic running accumulation uses a constant number of scalar variables, although storing the input is a separate concern.

AI Glossary / Mathematics and optimization / Intermediate

Kahan summation algorithm

Definition

The Kahan summation algorithm is a compensated method for adding floating-point numbers. It keeps a running sum and a correction that helps carry low-order information lost during an addition into later additions. It can substantially reduce accumulated rounding error compared with a simple left-to-right sum, but it does not make every result exact.

What it means

Computers store floating-point numbers using a finite number of significant bits. Near a large running total, a small addend may be too small to change the stored value. Repeating that operation can lose contributions that would matter when combined.
Kahan summation uses an extra accumulator to remember a correction associated with the rounded addition. This is a numerical technique, not an increase in the nominal storage precision of each number. It addresses errors in the accumulation process; it cannot recreate information already lost when inputs were measured, calculated, or converted to floating point.

How it works

Initialize the sum s and correction c to zero. For each input x, calculate y=x-c, then t=s+y, then c=(t-s)-y, and finally s=t. Return s. The order of these floating-point operations is part of the algorithm.
The correction in this convention has the sign of the rounding discrepancy, so it is subtracted from the next input. Other compensated-summation formulations use different signs or additional accumulators. Algebraically simplifying the correction as though arithmetic were exact can remove the mechanism. Preserve the intended evaluation behavior when compiler settings permit reassociation.

Three practical examples

A simulation can use compensated accumulation when adding many small contributions to a much larger running quantity.
A numerical analysis pipeline can compare ordinary and compensated totals when values span very different magnitudes.
A machine-learning evaluation can inspect accumulation error in large aggregate metrics, while keeping separate any errors arising in the metric values before they are summed.

Think of it this way

Think of keeping a small change tray beside a cash total whose display only shows coarse increments. Individual tiny contributions might not alter the display, but the tray lets several contributions combine into a visible increment. The analogy is limited: floating-point spacing varies with magnitude, and the correction is itself stored with finite precision.

Worked example

Consider an original example using binary64 arithmetic with round-to-nearest, ties-to-even. Let B=2^53=9,007,199,254,740,992, and add the sequence B, 1, 1. The exact mathematical answer is B+2.
At B and immediately above it, adjacent binary64 values are spaced by 2. The number B+1 lies halfway between B and B+2, so ties-to-even rounds B+1 to B. A naive left-to-right sum first stores B, then loses the first 1, then loses the second 1 for the same reason. Its result remains B.
Now trace Kahan summation. After processing B, the state is s=B and c=0. For the first 1, y=1 and t rounds to B. The correction becomes c=(B-B)-1=-1. The stored sum is still B, but the correction records the discrepancy.
For the second 1, y=1-(-1)=2. The addition t=B+2 is exactly representable. The new correction is ((B+2)-B)-2=0. The returned sum is B+2, recovering the contribution that naive summation lost. Executing the stated recurrence with binary64 values confirmed these intermediate states and both final totals.
This success does not establish universal exactness. As a separate counterexample, the sequence 10^16, 1, -10^16 has exact sum 1, but the same basic Kahan recurrence in the tested binary64 arithmetic returns 0. After the small contribution is recorded, forming the next corrected large negative input can itself round away the correction. More robust variants, different summation strategies, or greater precision may be needed.
Input order also matters for the naive method: summing the two ones before adding B produces B+2 in this example. However, reordering is not a universal solution for mixed signs, parallel reductions, or all accuracy requirements. The useful lesson is to choose and test the accumulation method under an explicit arithmetic model rather than assuming that addition order is irrelevant.

Illustrative case study

In a fictional environmental-simulation project, Willow Bay Analytics aggregates many small modeled contributions. The team notices that the last digits of totals change when work is divided into different batches. It compares a simple loop, a compensated loop, and a higher-precision reference on representative inputs.
The analysts document the chosen method and measure its additional cost. They also check whether the observed numerical difference affects the reported scientific conclusion. This fictional case illustrates verification and does not claim a measured speed or accuracy improvement for a real organization.

Common misconceptions and mistakes

Do not describe the algorithm as storing all rounding errors exactly. Its correction is also subject to rounding. Severe cancellation, overflow, nonfinite inputs, and extreme scale differences require additional attention. Nor can compensation fix inaccurate inputs.
Do not replace the operation sequence with an algebraically equivalent expression without considering floating-point evaluation. Avoid assuming that a language's built-in sum uses Kahan summation; behavior depends on the implementation and version. A parallel reduction also needs a deliberate strategy for combining partial results and their corrections.

Business use

Business value comes from more trustworthy numerical totals when accumulation error is material. Benchmark both accuracy and cost on realistic data distributions. Compare against a suitable reference and report absolute as well as relative error when the true total may be close to zero. Where exact decimal or integer semantics are required, choose an appropriate representation instead of assuming that compensation changes binary floating point into exact decimal arithmetic.

Check your understanding

What does c=-1 mean after adding the first 1 to B in the example?

Answer: The rounded addition fell short by 1. Subtracting that negative correction from the next input increases the next adjusted addend accordingly.

Related terms

Floating-point arithmetic
Rounding error
Compensated summation
Pairwise summation
Numerical stability
Cancellation
Machine precision
Neumaier summation
Reproducibility

Learn next

Repeat the B,1,1 example with B=2^52 and explain why the naive result changes. Then test mixed-sign sequences against an exact or higher-precision reference, recording the operation order and arithmetic precision rather than only the final displayed number.

Sources

Primary source: Kahan, How Futile are Mindless Assessments of Roundoff in Floating-Point Computation?, especially compiler reassociation and compensated sums: https://people.eecs.berkeley.edu/~wkahan/Mindless.pdf . Instructor recurrence: https://eli.sdsu.edu/courses/fall16/cs696/notes/D05MemoryAddition.pdf . Binary64 examples are original and were executed independently.

Previous: K-optimal pattern discovery Next: Kaiser - Meyer - Olkin test