HOME Mathematics Computer Science
Kahan Summation
Kahan Summation

Introduction
  • Kahan Summation is an algorithm that sums a set of floating point numbers while reducing the affects of rounding errors.
  • It works by keeping track of the error produced by the previous iteration, and compensating for it in the current iteration.
Simple Approach
A = [.1, .1, .1, .1, .1, .1, .1, .1, .1, .1]

total = 0
for a in A:
    total += a

print(total)
This algorithm results in a total of 0.9999999999999999
Kahan Summation
A = [.1, .1, .1, .1, .1, .1, .1, .1, .1, .1]

total = 0.0
error = 0.0
for a in A:
    errorAdjustedA = a - error
    tempTotal = total + errorAdjustedA
    error = (tempTotal - total) - errorAdjustedA
    total = tempTotal

print(total)
This algorithm results in a total of 1.0
Notes
  • Kahan Summation is also called 'Compensated Summation'
  • While Kahan Summation produces dramatically better results over the simple approach, it does use 4 times as many arithmetic operations and is therefore slower.