Kahan summation algorithm

The Kahan summation algorithm, also called compensated summation, is a technique from numerical analysis that greatly reduces the error in the total obtained by adding a sequence of finite-precision floating-point numbers, compared with the naive approach of adding them one after another. It does this by keeping a separate running compensation, a variable that accumulates the small errors lost at each addition, which in effect extends the precision of the sum by the precision of the compensation variable. Simply summing n numbers in sequence has a worst-case error that grows in proportion to n, and a root mean square error that grows as the square root of n for random inputs, because the roundoff errors form a random walk. With a compensation variable of sufficiently high precision, the worst-case error bound is effectively independent of n, so a large number of values can be summed with an error that depends only on the floating-point precision of the result. The algorithm is attributed to William Kahan, and Ivo Babuška seems to have devised a similar algorithm independently, hence the alternative name Kahan-Babuška summation.