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)

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)

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.