Kahan Summation Algorithm - Alternatives

Alternatives

Although Kahan's algorithm achieves error growth for summing n numbers, only slightly worse growth can be achieved by pairwise summation: one recursively divides the set of numbers into two halves, sums each half, and then adds the two sums. This has the advantage of requiring the same number of arithmetic operations as the naive summation (unlike Kahan's algorithm, which requires four times the arithmetic and has a latency of four times a simple summation) and can be calculated in parallel. The base case of the recursion could in principle be the sum of only one (or zero) numbers, but to amortize the overhead of recursion one would normally use a larger base case. The equivalent of pairwise summation is used in many fast Fourier transform (FFT) algorithms, and is responsible for the logarithmic growth of roundoff errors in those FFTs. In practice, with roundoff errors of random signs, the root mean square errors of pairwise summation actually grow as .

Another alternative is to use arbitrary precision arithmetic, which in principle need do no rounding at all at the cost of much greater computational effort. A way of performing exactly rounded sums using arbitrary precision that is extended adaptively using multiple floating-point components, to minimize computational cost in common cases where high precision is not needed, was described by Shewchuk. Another method that uses only integer arithmetic, but a large accumulator was described by Kirchner and Kulisch; a hardware implementation was described by Müller, Rüb and Rülling.

Also an alternative, especially in accountancy is, to use fix point arithmetic with a suitable base ($0.01 or $0.0001) instead of floating point arithmetic with $1 as base.