Editing Kahan summation algorithm (section)

{{Short description|Algorithm in numerical analysis}}
In [[numerical analysis]], the '''Kahan summation algorithm''', also known as '''compensated summation''',<ref>Strictly, there exist other variants of compensated summation as well: see {{cite book |first=Nicholas |last=Higham |title=Accuracy and Stability of Numerical Algorithms (2 ed) |publisher=SIAM |year=2002 |pages=110–123 |isbn=978-0-89871-521-7}}</ref> significantly reduces the [[numerical error]] in the total obtained by adding a [[sequence]] of finite-[[decimal precision|precision]] [[floating-point number]]s, compared to the naive 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 <math>n</math> numbers in sequence has a worst-case error that grows proportional to <math>n</math>, and a [[root mean square]] error that grows as <math>\sqrt{n}</math> for random inputs (the roundoff errors form a [[random walk]]).<ref name=Higham93>{{Citation | title=The accuracy of floating point summation | first1=Nicholas J. | last1=Higham | journal=[[SIAM Journal on Scientific Computing]] | volume=14 | issue=4 | pages=783–799 | doi=10.1137/0914050 | year=1993 | bibcode=1993SJSC...14..783H | citeseerx=10.1.1.43.3535 | s2cid=14071038 }}.</ref>  With compensated summation, using a compensation variable with sufficiently high precision the worst-case error bound is effectively independent of <math>n</math>, so a large number of values can be summed with an error that only depends on the floating-point [[precision (arithmetic)|precision]] of the result.<ref name=Higham93/>

The [[algorithm]] is attributed to [[William Kahan]];<ref name="kahan65">{{Citation |last=Kahan |first=William |title=Further remarks on reducing truncation errors |date=January 1965 |url=http://mgnet.org/~douglas/Classes/na-sc/notes/kahan.pdf |journal=[[Communications of the ACM]] |volume=8 |issue=1 |page=40 |archive-url=https://web.archive.org/web/20180209003010/http://mgnet.org/~douglas/Classes/na-sc/notes/kahan.pdf |doi=10.1145/363707.363723 |s2cid=22584810 |archive-date=9 February 2018}}.</ref> [[Ivo Babuška]] seems to have come up with a similar algorithm independently (hence '''Kahan&ndash;Babuška summation''').<ref>Babuska, I.: Numerical stability in mathematical analysis. Inf. Proc. ˇ 68, 11–23 (1969)</ref> 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<ref>{{cite journal |first=Jack E. |last=Bresenham |url=http://www.research.ibm.com/journal/sj/041/ibmsjIVRIC.pdf |title=Algorithm for computer control of a digital plotter |journal=IBM Systems Journal |volume=4 |issue=1 |date=January 1965 |pages=25–30 |doi=10.1147/sj.41.0025 |s2cid=41898371 }}</ref>) and the [[delta-sigma modulation]].<ref>{{cite journal |first1=H. |last1=Inose |first2=Y. |last2=Yasuda |first3=J. |last3=Murakami |title=A Telemetering System by Code Manipulation – ΔΣ Modulation |journal=IRE Transactions on Space Electronics and Telemetry |date=September 1962 |pages=204–209|volume=SET-8|  doi=10.1109/IRET-SET.1962.5008839 |s2cid=51647729 }}</ref>