Kahan summation algorithm

In numerical analysis, the Kahan summation algorithm, also known as compensated summation,^[1] significantly reduces the numerical error in the total obtained by adding a sequence of finite-precision floating-point numbers, compared to the obvious approach. This is done by keeping a separate running compensation (a variable to accumulate small errors), in effect extending the precision of the sum by the precision of the compensation variable.

In particular, simply summing $n$ numbers in sequence has a worst-case error that grows proportional to $n$ , and a root mean square error that grows as ${\sqrt {n}}$ for random inputs (the roundoff errors form a random walk).^[2] With compensated summation, using a compensation variable with 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 only depends on the floating-point precision of the result.^[2]

The algorithm is attributed to William Kahan;^[3] Ivo Babuška seems to have come up with a similar algorithm independently (hence Kahan–Babuška summation).^[4] Similar, earlier techniques are, for example, Bresenham's line algorithm, keeping track of the accumulated error in integer operations (although first documented around the same time^[5]) and the delta-sigma modulation.^[6]

^ Strictly, there exist other variants of compensated summation as well: see Higham, Nicholas (2002). Accuracy and Stability of Numerical Algorithms (2 ed). SIAM. pp. 110–123. ISBN 978-0-89871-521-7.
^ ^a ^b Higham, Nicholas J. (1993), "The accuracy of floating point summation", SIAM Journal on Scientific Computing, 14 (4): 783–799, Bibcode:1993SJSC...14..783H, CiteSeerX 10.1.1.43.3535, doi:10.1137/0914050, S2CID 14071038.
^ Kahan, William (January 1965), "Further remarks on reducing truncation errors" (PDF), Communications of the ACM, 8 (1): 40, doi:10.1145/363707.363723, S2CID 22584810, archived from the original (PDF) on 9 February 2018.
^ Babuska, I.: Numerical stability in mathematical analysis. Inf. Proc. ˇ 68, 11–23 (1969)
^ Bresenham, Jack E. (January 1965). "Algorithm for computer control of a digital plotter" (PDF). IBM Systems Journal. 4 (1): 25–30. doi:10.1147/sj.41.0025. S2CID 41898371.
^ Inose, H.; Yasuda, Y.; Murakami, J. (September 1962). "A Telemetering System by Code Manipulation – ΔΣ Modulation". IRE Transactions on Space Electronics and Telemetry. SET-8: 204–209. doi:10.1109/IRET-SET.1962.5008839. S2CID 51647729.

[1] Strictly, there exist other variants of compensated summation as well: see Higham, Nicholas (2002). Accuracy and Stability of Numerical Algorithms (2 ed). SIAM. pp. 110–123. ISBN 978-0-89871-521-7.

[Higham93-2] Higham, Nicholas J. (1993), "The accuracy of floating point summation", SIAM Journal on Scientific Computing, 14 (4): 783–799, Bibcode:1993SJSC...14..783H, CiteSeerX 10.1.1.43.3535, doi:10.1137/0914050, S2CID 14071038.

[kahan65-3] Kahan, William (January 1965), "Further remarks on reducing truncation errors" (PDF), Communications of the ACM, 8 (1): 40, doi:10.1145/363707.363723, S2CID 22584810, archived from the original (PDF) on 9 February 2018.

[4] Babuska, I.: Numerical stability in mathematical analysis. Inf. Proc. ˇ 68, 11–23 (1969)

[5] Bresenham, Jack E. (January 1965). "Algorithm for computer control of a digital plotter" (PDF). IBM Systems Journal. 4 (1): 25–30. doi:10.1147/sj.41.0025. S2CID 41898371.

[6] Inose, H.; Yasuda, Y.; Murakami, J. (September 1962). "A Telemetering System by Code Manipulation – ΔΣ Modulation". IRE Transactions on Space Electronics and Telemetry. SET-8: 204–209. doi:10.1109/IRET-SET.1962.5008839. S2CID 51647729.

[1]

[2]

[3]

[4]

[5]

[6]

Kahan summation algorithm

From Wikipedia, the free encyclopedia · View on Wikipedia