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.