Kahan summation algorithm
In numerical analysis, the Kahan summation algorithm, also known as compensated summation, 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.
- Comment
- enIn numerical analysis, the Kahan summation algorithm, also known as compensated summation, 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.
- Has abstract
- enIn numerical analysis, the Kahan summation algorithm, also known as compensated summation, 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 numbers in sequence has a worst-case error that grows proportional to , and a root mean square error that grows as for random inputs (the roundoff errors form a random walk). With compensated summation, using a compensation variable with sufficiently high precision the worst-case error bound is effectively independent of , so a large number of values can be summed with an error that only depends on the floating-point precision of the result. The algorithm is attributed to William Kahan; Ivo Babuška seems to have come up with a similar algorithm independently (hence Kahan–Babuška summation). 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) and the delta-sigma modulation.
- Is primary topic of
- Kahan summation algorithm
- Label
- enKahan summation algorithm
- Link from a Wikipage to an external page
- www.ddj.com/cpp/184403224
- www.nuget.org/packages/HPCsharp
- docs.python.org/library/math.html%23math.fsum
- Link from a Wikipage to another Wikipage
- 2Sum
- Algorithm
- Algorithms for calculating variance
- ANSI C
- Arbitrary-precision
- Arbitrary-precision arithmetic
- Associativity
- Backwards stable
- BLAS
- Bresenham's line algorithm
- Category:Articles with example pseudocode
- Category:Computer arithmetic
- Category:Numerical analysis
- Compiler optimization
- Condition number
- C programming language
- C Sharp (programming language)
- Decimal precision
- Delta-sigma modulation
- Double-precision
- Fast Fourier transform
- Floating-point arithmetic
- Floating-point number
- Fortran
- Intel C++ Compiler
- Ivo Babuška
- Jonathan Shewchuk
- Julia (programming language)
- K&R C
- Linear algebra
- Machine epsilon
- Machine precision
- Non-negative
- Numerical analysis
- Numerical error
- Pairwise summation
- Precision (arithmetic)
- Pseudocode
- Python (programming language)
- Quadruple precision
- Random walk
- Recursively
- Relative error
- Root mean square
- Sequence
- SIMD
- Ulrich W. Kulisch
- Volatile variable
- William Kahan
- SameAs
- 2m5Pj
- Algoritmo di sommatoria di Kahan
- Algorytm sumacyjny Kahana
- Kahanen batuketa-algoritmo
- Kahano sudėties algoritmas
- m.020q8n
- Q2982293
- Алгоритм Кехена
- Алгоритм Кэхэна
- カハンの加算アルゴリズム
- Subject
- Category:Articles with example pseudocode
- Category:Computer arithmetic
- Category:Numerical analysis
- WasDerivedFrom
- Kahan summation algorithm?oldid=1114844162&ns=0
- WikiPageLength
- 26282
- Wikipage page ID
- 373216
- Wikipage revision ID
- 1114844162
- WikiPageUsesTemplate
- Template:Citation needed
- Template:Confusing
- Template:Reflist