Kahan Summation Algorithm - The Algorithm

The Algorithm

In pseudocode, the algorithm is:

function KahanSum(input) var sum = 0.0 var c = 0.0 //A running compensation for lost low-order bits. for i = 1 to input.length do y = input - c //So far, so good: c is zero. t = sum + y //Alas, sum is big, y small, so low-order digits of y are lost. c = (t - sum) - y //(t - sum) recovers the high-order part of y; subtracting y recovers -(low part of y) sum = t //Algebraically, c should always be zero. Beware eagerly optimising compilers! //Next time around, the lost low part will be added to y in a fresh attempt. return sum