The SDL Component Suite is an industry leading collection of components supporting scientific and engineering computing. Please visit the SDL Web site for more information....



TKahanSum


When adding a large number of floating point numbers the finite precision of these values may result in considerable round-off errors. In particular the "normal" summation of N numbers shows an error which is proportional to N. The Kahan summation algorithm significantly reduces the numerical error of the sum, leading in effect to an error which only depends on the floating point precision and which is independent of N.

The Kahan algorithm (also called "compensation algorithm") is based on a separate running compensation variable which accumulates small errors. The algorithm is attributed to William Kahan.1)

The general approach of calculating an error-compensated sum is first to use the Reset method to clear the sum, then add all terms to be added by the method Add. The error-compensated sum can be obtained by reading the public variable Sum.

Example: The following example demonstrates the error which accumulates when summing 10 million random numbers. The "normal" summation results in 4999906.03882061 while the Kahan sum yields 4999906.03949656, which represents the correct sum within the limits of the available floating point precision (15 digits).
const
  LENG = 10000000;

var
  i    : integer;
  sum  : double;
  KS   : TKahanSum;

begin
RandSeed := 0;
SetLength(values,LENG);
for i:=1 to LENG do  // fill in random values
  values[i-1] := random;

sum := 0;
for i:=1 to LENG do  // calculate the "normal" sum
  sum := sum + values[i-1];
// at this point the variable "sum" holds the result of
// "normal" summation and is shown by a TLabel component
LblSum.Caption := floattostr(sum);

KS := TKahanSum.Create(nil);  // calculate the Kahan sum
KS.Reset;
for i:=1 to LENG do
  KS.Add(values[i-1]);
// display the Kahan sum by another TLabel component
LblKSum.Caption := floattostr(KS.Sum);
KS.Free;
end;



1) Kahan, William (January 1965), "Further remarks on reducing truncation errors", Communications of the ACM 8 (1): 40.


Last Update: 2013-Oct-22