In
numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of numerical methods t ...
, 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
In mathematics and its applications, the root mean square of a set of numbers x_i (abbreviated as RMS, or rms and denoted in formulas as either x_\mathrm or \mathrm_x) is defined as the square root of the mean square (the arithmetic mean of the ...
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
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
is attributed to William Kahan
William "Velvel" Morton Kahan (born June 5, 1933) is a Canadian mathematician and computer scientist, who received the Turing Award in 1989 for "''his fundamental contributions to numerical analysis''",
was named an ACM Fellow in 1994, and induc ...
;[.] 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
Bresenham's line algorithm is a line drawing algorithm that determines the points of an ''n''-dimensional raster that should be selected in order to form a close approximation to a straight line between two points. It is commonly used to draw li ...
, keeping track of the accumulated error in integer operations (although first documented around the same time) and the delta-sigma modulation
Delta-sigma (ΔΣ; or sigma-delta, ΣΔ) modulation is a method for encoding analog signals into digital signals as found in an analog-to-digital converter (ADC). It is also used to convert high bit-count, low-frequency digital signals into l ...
.
The algorithm
In pseudocode
In computer science, pseudocode is a plain language description of the steps in an algorithm or another system. Pseudocode often uses structural conventions of a normal programming language, but is intended for human reading rather than machine re ...
, the algorithm will be:
function KahanSum(input)
var sum = 0.0 // Prepare the accumulator.
var c = 0.0 // A running compensation for lost low-order bits.
for i = 1 to input.length do // The array ''input'' has elements indexed input to input nput.length
var y = input - c // ''c'' is zero the first time around.
var t = sum + y // Alas, ''sum'' is big, ''y'' small, so low-order digits of ''y'' are lost.
c = (t - sum) - y // ''(t - sum)'' cancels the high-order part of ''y''; subtracting ''y'' recovers negative (low part of ''y'')
sum = t // Algebraically, ''c'' should always be zero. Beware overly-aggressive optimizing compilers!
next i // Next time around, the lost low part will be added to ''y'' in a fresh attempt.
return sum
This algorithm can also be rewritten to use the Fast2Sum algorithm:
function KahanSum2(input)
var sum = 0.0 // Prepare the accumulator.
var c = 0.0 // A running compensation for lost low-order bits.
for i = 1 to input.length do // The array ''input'' has elements indexed input to input nput.length
var y = input + c // ''c'' is zero the first time around.
(sum,c) = Fast2Sum(sum,y) // ''sum'' + ''c'' is an approximation to the exact sum.
next i // Next time around, the lost low part will be added to ''y'' in a fresh attempt.
return sum
Worked example
This example will be given in decimal. Computers typically use binary arithmetic, but the principle being illustrated is the same. Suppose we are using six-digit decimal floating-point arithmetic
In computing, floating-point arithmetic (FP) is arithmetic that represents real numbers approximately, using an integer with a fixed precision, called the significand, scaled by an integer exponent of a fixed base. For example, 12.345 can be r ...
, sum
has attained the value 10000.0, and the next two values of input /code> are 3.14159 and 2.71828. The exact result is 10005.85987, which rounds to 10005.9. With a plain summation, each incoming value would be aligned with sum
, and many low-order digits would be lost (by truncation or rounding). The first result, after rounding, would be 10003.1. The second result would be 10005.81828 before rounding and 10005.8 after rounding. This is not correct.
However, with compensated summation, we get the correct rounded result of 10005.9.
Assume that c
has the initial value zero.
y = 3.14159 - 0.00000 ''y = input - c''
t = 10000.0 + 3.14159
= 10003.14159 But only six digits are retained.
= 10003.1 Many digits have been lost!
c = (10003.1 - 10000.0) - 3.14159 This must be evaluated as written!
= 3.10000 - 3.14159 The assimilated part of ''y'' recovered, vs. the original full ''y''.
= -0.0415900 Trailing zeros shown because this is six-digit arithmetic.
sum = 10003.1 Thus, few digits from ''input(i'') met those of ''sum''.
The sum is so large that only the high-order digits of the input numbers are being accumulated. But on the next step, c
gives the error.
y = 2.71828 - (-0.0415900) The shortfall from the previous stage gets included.
= 2.75987 It is of a size similar to ''y'': most digits meet.
t = 10003.1 + 2.75987 But few meet the digits of ''sum''.
= 10005.85987 And the result is rounded
= 10005.9 To six digits.
c = (10005.9 - 10003.1) - 2.75987 This extracts whatever went in.
= 2.80000 - 2.75987 In this case, too much.
= 0.040130 But no matter, the excess would be subtracted off next time.
sum = 10005.9 Exact result is 10005.85987, this is correctly rounded to 6 digits.
So the summation is performed with two accumulators: sum
holds the sum, and c
accumulates the parts not assimilated into sum
, to nudge the low-order part of sum
the next time around. Thus the summation proceeds with "guard digits" in c
, which is better than not having any, but is not as good as performing the calculations with double the precision of the input. However, simply increasing the precision of the calculations is not practical in general; if input
is already in double precision, few systems supply quadruple precision, and if they did, input
could then be in quadruple precision.
Accuracy
A careful analysis of the errors in compensated summation is needed to appreciate its accuracy characteristics. While it is more accurate than naive summation, it can still give large relative errors for ill-conditioned sums.
Suppose that one is summing values , for . The exact sum is
: (computed with infinite precision).
With compensated summation, one instead obtains , where the error is bounded by[
:
where is the ]machine precision
Machine epsilon or machine precision is an upper bound on the relative approximation error due to rounding in floating point arithmetic. This value characterizes computer arithmetic in the field of numerical analysis, and by extension in the subje ...
of the arithmetic being employed (e.g. for IEEE standard double-precision
Double-precision floating-point format (sometimes called FP64 or float64) is a floating-point number format, usually occupying 64 bits in computer memory; it represents a wide dynamic range of numeric values by using a floating radix point.
Flo ...
floating point). Usually, the quantity of interest is the relative error
The approximation error in a data value is the discrepancy between an exact value and some ''approximation'' to it. This error can be expressed as an absolute error (the numerical amount of the discrepancy) or as a relative error (the absolute er ...
, which is therefore bounded above by
:
In the expression for the relative error bound, the fraction is the condition number
In numerical analysis, the condition number of a function measures how much the output value of the function can change for a small change in the input argument. This is used to measure how sensitive a function is to changes or errors in the inpu ...
of the summation problem. Essentially, the condition number represents the ''intrinsic'' sensitivity of the summation problem to errors, regardless of how it is computed. The relative error bound of ''every'' ( backwards stable) summation method by a fixed algorithm in fixed precision (i.e. not those that use arbitrary-precision
In computer science, arbitrary-precision arithmetic, also called bignum arithmetic, multiple-precision arithmetic, or sometimes infinite-precision arithmetic, indicates that calculations are performed on numbers whose digits of precision are li ...
arithmetic, nor algorithms whose memory and time requirements change based on the data), is proportional to this condition number.[ An ''ill-conditioned'' summation problem is one in which this ratio is large, and in this case even compensated summation can have a large relative error. For example, if the summands are uncorrelated random numbers with zero mean, the sum is a random walk, and the condition number will grow proportional to . On the other hand, for random inputs with nonzero mean the condition number asymptotes to a finite constant as . If the inputs are all ]non-negative
In mathematics, the sign of a real number is its property of being either positive, negative, or zero. Depending on local conventions, zero may be considered as being neither positive nor negative (having no sign or a unique third sign), or i ...
, then the condition number is 1.
Given a condition number, the relative error of compensated summation is effectively independent of . In principle, there is the that grows linearly with , but in practice this term is effectively zero: since the final result is rounded to a precision , the term rounds to zero, unless is roughly or larger.[ In double precision, this corresponds to an of roughly , much larger than most sums. So, for a fixed condition number, the errors of compensated summation are effectively , independent of .
In comparison, the relative error bound for naive summation (simply adding the numbers in sequence, rounding at each step) grows as multiplied by the condition number.][ This worst-case error is rarely observed in practice, however, because it only occurs if the rounding errors are all in the same direction. In practice, it is much more likely that the rounding errors have a random sign, with zero mean, so that they form a random walk; in this case, naive summation has a ]root mean square
In mathematics and its applications, the root mean square of a set of numbers x_i (abbreviated as RMS, or rms and denoted in formulas as either x_\mathrm or \mathrm_x) is defined as the square root of the mean square (the arithmetic mean of the ...
relative error that grows as multiplied by the condition number.[Manfred Tasche and Hansmartin Zeuner, ''Handbook of Analytic-Computational Methods in Applied Mathematics'', Boca Raton, FL: CRC Press, 2000.] This is still much worse than compensated summation, however. However, if the sum can be performed in twice the precision, then is replaced by , and naive summation has a worst-case error comparable to the term in compensated summation at the original precision.
By the same token, the that appears in above is a worst-case bound that occurs only if all the rounding errors have the same sign (and are of maximal possible magnitude).[ In practice, it is more likely that the errors have random sign, in which case terms in are replaced by a random walk, in which case, even for random inputs with zero mean, the error grows only as (ignoring the term), the same rate the sum grows, canceling the factors when the relative error is computed. So, even for asymptotically ill-conditioned sums, the relative error for compensated summation can often be much smaller than a worst-case analysis might suggest.
]
Further enhancements
Neumaier introduced an improved version of Kahan algorithm, which he calls an "improved Kahan–Babuška algorithm", which also covers the case when the next term to be added is larger in absolute value than the running sum, effectively swapping the role of what is large and what is small. In pseudocode
In computer science, pseudocode is a plain language description of the steps in an algorithm or another system. Pseudocode often uses structural conventions of a normal programming language, but is intended for human reading rather than machine re ...
, the algorithm is:
function KahanBabushkaNeumaierSum(input)
var sum = 0.0
var c = 0.0 // A running compensation for lost low-order bits.
for i = 1 to input.length do
var t = sum + input if , sum, >= , input then
c += (sum - t) + input // If ''sum'' is bigger, low-order digits of ''input ' are lost.
else
c += (input - t) + sum // Else low-order digits of ''sum'' are lost.
endif
sum = t
next i
return sum + c // Correction only applied once in the very end.
This enhancement is similar to the replacement of Fast2Sum by 2Sum
2Sum is a floating-point algorithm for computing the exact round-off error in a floating-point addition operation.
2Sum and its variant Fast2Sum were first published by Møller in 1965.
Fast2Sum is often used implicitly in other algorithms such a ...
in Kahan's algorithm rewritten with Fast2Sum.
For many sequences of numbers, both algorithms agree, but a simple example due to Peters shows how they can differ. For summing