Kahan summation algorithm

In <a href="/facts/Numerical_analysis/QT9cYa9z">numerical analysis</a>, the Kahan summation algorithm, also known as compensated summation, significantly reduces the <a href="/facts/Numerical_error/5x9tkosI">numerical error</a> in the total obtained by adding a <a href="/facts/Sequence/gV2S4uqp">sequence</a> of finite-<a href="/facts/Decimal_precision/RUfYtpgo">precision</a> <a href="/facts/Floating-point_number/eIckahxe">floating-point numbers</a>, 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 
 
 
 
 n
 
 
 {\displaystyle n}
 
 numbers in sequence has a worst-case error that grows proportional to 
 
 
 
 n
 
 
 {\displaystyle n}
 
, and a <a href="/facts/Root_mean_square/Cfmg7dws">root mean square</a> error that grows as 
 
 
 
 
 
 n
 
 
 
 
 {\displaystyle {\sqrt {n}}}
 
 for random inputs (the roundoff errors form a <a href="/facts/Random_walk/08v0jmfv">random walk</a>). With compensated summation, using a compensation variable with sufficiently high precision the worst-case error bound is effectively independent of 
 
 
 
 n
 
 
 {\displaystyle n}
 
, so a large number of values can be summed with an error that only depends on the floating-point <a href="/facts/Precision_(arithmetic)/RUfYtpgo">precision</a> of the result.
The <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> is attributed to <a href="/facts/William_Kahan/J1GNQDyN">William Kahan</a>; <a href="/facts/Ivo_Babu%25C5%25A1ka/G5NbtybI">Ivo Babuška</a> seems to have come up with a similar algorithm independently (hence Kahan–Babuška summation). Similar, earlier techniques are, for example, <a href="/facts/Bresenham%2527s_line_algorithm/G1fcMKEF">Bresenham's line algorithm</a>, keeping track of the accumulated error in integer operations (although first documented around the same time) and the <a href="/facts/Delta-sigma_modulation/QrhBCoUe">delta-sigma modulation</a>.

Kahan summation algorithm open-in-new

Kahan summation algorithm