How to Learn Compensated Summation: Kahan, Neumaier, Floating-Point Error and Reproducible Reductions

Wait, What?

On a computer, adding the same numbers in a different order can produce a different answer.

That sounds impossible if you learned arithmetic as exact algebra. But floating-point addition is rounded after operations, so it is generally not associative: (a+b)+c need not equal a+(b+c).

Compensated summation algorithms such as Kahan’s method teach a professional numerical lesson: sometimes the main algorithm is trivial—“add the numbers”—but the representation of numbers makes the implementation mathematically non-trivial.

Quick Answer

Learn compensated summation in this order: binary floating point → rounding → loss of low-order bits → non-associativity → naive summation error → pairwise summation → Kahan compensation → Neumaier refinement → condition number → accurate library routines → vectorisation/parallel reduction → reproducibility.

1. Start With the Representation Problem

A binary floating-point number stores a finite significand and exponent. Many ordinary decimal fractions cannot be represented exactly in binary, and even exactly representable inputs can produce rounded intermediate results when their magnitudes differ greatly.

The key point is not that floating point is “bad.” It is that floating point is a finite numerical model with precise rules and limits. Good numerical algorithms are designed around those limits.

2. Why Small Terms Can Disappear

Suppose a running sum is very large while the next term is tiny. The exact sum may require more significant bits than the floating-point format can store. When the result is rounded back to working precision, part or all of the small term can vanish.

If this happens repeatedly, naive left-to-right summation can lose information many times.

3. Non-Associativity Is the First Experiment to Run

Try a set of values containing both very large and very small magnitudes. Sum them in the original order, reversed order, sorted by magnitude and with a high-accuracy library routine. If the results differ, you have observed the real computational problem.

This is why parallel programs can produce different low-order bits when work is reduced in different tree orders. The mathematical sum is order-independent; the sequence of rounded machine additions is not.

4. Naive Summation Is a Real Algorithm With an Error Model

s = 0.0
for x in values:
    s = s + x
return s

This loop is fast, simple and often good enough. The mistake is not using it. The mistake is assuming that because the pseudocode looks obvious, its numerical error is irrelevant.

For long or ill-conditioned sums, the accumulation of rounding error can matter materially.

5. Pairwise Summation Changes the Error Growth

Instead of adding strictly left-to-right, recursively split the values and combine partial sums:

pairwise_sum(a[l:r]):
    if small enough:
        sum directly
    else:
        m = midpoint
        return pairwise_sum(a[l:m]) + pairwise_sum(a[m:r])

A balanced reduction keeps the addition tree shallow and often improves numerical behaviour. It also maps naturally onto parallel execution. Pairwise summation and compensated summation are different tools; one does not make the other obsolete.

6. Kahan’s Core Idea: Keep a Compensation for Lost Low Bits

Kahan summation maintains an extra variable that tracks rounding information lost from previous additions:

sum = 0.0
c = 0.0

for x in values:
    y = x - c
    t = sum + y
    c = (t - sum) - y
    sum = t

return sum

The compensation c is not a second full-precision accumulator. It estimates the low-order part discarded during the rounded addition and feeds that information into a later step.

7. Trace One Iteration Before Trusting the Formula

The expression t - sum asks what portion of the compensated addend actually survived the rounded addition. Subtracting y then estimates what was lost. On the next iteration, that loss is subtracted from the new input so it can re-enter the running total.

This is exactly the kind of algorithm that learners should trace with deliberately awkward magnitudes. Reading the four lines without observing low-order bits disappear makes the method seem like a trick.

8. Compensation Does Not Make Floating Point Exact

Kahan summation substantially improves error behaviour, but it does not turn finite-precision arithmetic into exact real arithmetic. Error still depends on rounding, data conditioning and implementation details.

A professional explanation therefore says “more accurate under a well-understood error bound,” not “fixes floating point.”

9. Learn the Condition Number of a Sum

For exact sum S of values xᵢ, a useful conditioning measure is:

condition ≈ sum(|x_i|) / |sum(x_i)|

If positive and negative terms nearly cancel, the denominator can become tiny while the numerator remains large. The problem is then ill-conditioned: even very small rounding errors can become large relative errors in the final result.

This distinction is critical. Algorithmic stability cannot remove information that the mathematical problem itself makes extremely sensitive.

10. Neumaier’s Refinement Handles a Difficult Case Better

A common refinement associated with Neumaier adjusts the compensation depending on which magnitude is larger:

sum = 0.0
c = 0.0

for x in values:
    t = sum + x
    if abs(sum) >= abs(x):
        c += (sum - t) + x
    else:
        c += (x - t) + sum
    sum = t

return sum + c

This can handle some cancellation patterns that defeat the original Kahan loop. The important learning point is broader than the exact branch: compensated algorithms form a family with different accuracy/performance trade-offs.

11. Order Still Matters

Sorting values by magnitude before summation can improve some cases, but sorting costs O(n log n), changes data order, and does not provide a universal solution for mixed-sign cancellation. Pairwise reduction, compensated summation and exact/faithful algorithms attack different aspects of the problem.

Choose a method based on accuracy requirements, performance budget, parallelism and reproducibility—not on one dramatic demo.

12. Compare Against an Accurate Reference

Python’s current math.fsum() documentation says it returns an accurate floating-point sum by tracking multiple intermediate partial sums. It is a useful reference implementation for experiments because it is designed for more accuracy than ordinary repeated +.

A good learner test harness compares:

naive left-to-right summation,
reverse-order summation,
pairwise summation,
Kahan summation,
Neumaier-style summation,
a high-accuracy reference such as math.fsum(),
and, for controlled tests, a higher-precision or exact arithmetic reference.

13. Error Should Be Measured, Not Eyeballed

For test data where a trustworthy reference is available, record absolute error, relative error and ulp-scale differences where appropriate. Also record the condition number estimate. A method that looks excellent on well-conditioned positive data may behave differently under cancellation.

14. Compiler Optimisation Can Change the Algorithm

Compensated summation depends on a specific sequence of rounded operations. Compiler options that freely reassociate floating-point expressions can invalidate that logic. “Fast math” modes may legally transform expressions in ways that are excellent for throughput but incompatible with the assumptions of compensation.

Professional numerical code therefore treats compiler floating-point semantics as part of the algorithm contract.

15. Vectorisation and Parallelism Need Deliberate Design

A sequential compensation dependency appears to resist SIMD and multicore execution, but modern work shows that compensated schemes can be vectorised and parallelised. One practical pattern uses independent compensated accumulators per lane or block and then combines partial sums carefully.

A 2023 study by Beata Dmitruk investigated vectorised and parallel Kahan/Gill–Møller implementations with AVX-512 and OpenMP, illustrating that higher accuracy and modern hardware utilisation do not have to be mutually exclusive.

16. Parallel Reduction Creates a Reproducibility Problem

If worker completion order changes, the reduction tree can change, and therefore the rounded result can change. This matters in scientific computing, simulation, validation and machine-learning workflows where bitwise reproducibility may be required for debugging or comparison.

Recent work continues to study the impact of floating-point non-associativity on reproducibility in HPC and deep-learning systems. When reproducibility is a requirement, specify it explicitly rather than assuming every parallel sum will be deterministic.

17. Kahan Is Not the Final Word on Accurate Summation

Research by Ogita, Rump and Oishi developed accurate summation and dot-product algorithms that can achieve results comparable to computations performed in higher working precision using carefully designed error-free transformations and compensation. Other algorithms pursue faithful rounding or order-independent reproducible accumulation.

Kahan is therefore best learned as the doorway into numerical summation, not as the ceiling.

18. Performance Has More Than One Axis

Measure:

throughput,
latency,
vectorisation,
parallel scalability,
absolute and relative error,
reproducibility across thread counts and runs,
memory traffic,
and behaviour under cancellation.

The fastest method on a benign benchmark may not be the best method for a numerically sensitive production pipeline.

19. Common Failure States

Believing floating-point addition is associative because real-number addition is.
Calling all discrepancies “precision problems” without locating the rounding mechanism.
Assuming Kahan summation makes the result exact.
Ignoring cancellation and the conditioning of the sum.
Testing only positive values of similar magnitude.
Comparing two floating-point methods without a higher-quality reference.
Enabling aggressive reassociation and assuming the compensation loop is unchanged.
Parallelising a sum without deciding whether reproducibility matters.
Choosing a numerically sophisticated method without measuring its actual cost on the target machine.

20. Practice Ladder: Beginner to Professional

Beginner: find three floating-point values for which two association orders produce different machine results.
Foundation: implement naive and Kahan summation, then trace the compensation variable after every element.
Intermediate: add pairwise and Neumaier methods; test positive, mixed-sign and strongly cancelling data sets.
Advanced: compare against math.fsum() or a high-precision reference and relate observed relative error to the condition number.
Professional: benchmark scalar, SIMD and parallel reductions under strict and relaxed compiler floating-point modes; test reproducibility across thread counts.
Transfer: explain why two programs can both be IEEE-754 compliant yet return different low-order bits for the same mathematical sum.

Learning Hall Boundary

This article owns floating-point summation as an algorithmic problem: non-associativity, pairwise reduction, Kahan/Neumaier compensation, conditioning and reproducible reduction. It does not replace the site’s general numerical-analysis, parallel-algorithm or programming-language material. Those remain separate foundations and applications.

Evidence Boundary

Nicholas Higham’s Accuracy and Stability of Numerical Algorithms provides a standard numerical-analysis treatment of summation error. Ogita, Rump and Oishi’s 2005 paper Accurate Sum and Dot Product develops stronger compensated approaches and error guarantees. Python 3.14’s current math.fsum() documentation describes accurate summation through multiple partial sums and notes relevant IEEE-754 assumptions. Dmitruk’s 2023 work examines vectorised and parallel compensated summation, while recent HPC research continues to document how floating-point non-associativity affects reproducibility.

Professional rule: you understand summation when you stop asking only “what is the Big-O?” and also ask “what arithmetic is actually executed, how sensitive is the problem, what error is acceptable, and must different execution orders reproduce the same bits?”