Kahan Summation

Introduction

Kahan summation algorithm, also known as compensated summation or carry-sum algorithm, is an algorithm used to reduce the error in the cumulative sum of a finite-precision floating-point sequence. It primarily achieves this by maintaining a separate variable to accumulate errors (commonly denoted as \(c\)).

This algorithm was mainly discovered by William Kahan in the 1960s. Since Ivo Babuška also independently proposed a similar algorithm, the Kahan summation algorithm is also known as the Kahan–Babuška summation algorithm.

Rounding Error

In computer programs, we need to approximate real numbers using a finite number of digits. Most modern computers use floating-point numbers specified by IEEE-754 for this approximation. For numbers like \(\frac{1}{3}\), since we cannot represent them exactly with a finite number of digits, they must be rounded (truncated) when using the IEEE-754 representation. This rounding error is a characteristic of floating-point computation.

In floating-point addition, commutativity holds, but associativity does not. That is, \(a+b = b+a\) but \((a+b)+c \neq a+(b+c)\). Therefore, when summing a sequence of floating-point numbers, we can accumulate them from left to right one by one, or we can pair them up in the original order. The second method is slower and requires more memory, and is often used by specific summation functions in some languages, but it yields more accurate results.

To obtain more accurate floating-point summation results, we need to use the Kahan summation algorithm.

When computing \(S_{new}=S_{old}+a\) (where \(a\) is a value in the floating-point sequence), define the actual value added to \(S\) as \(a_{eff}=S_{new}-S_{old}\). If \(a_{eff}\) is greater than \(a\), it indicates an upward rounding error; if \(a_{eff}\) is less than \(a\), it indicates a downward rounding error. The rounding error is defined as \(E_{roundoff} = a_{eff} - a\). Then the value used to correct this rounding error is \(a-a_{eff}\), which is the negative of \(E_{roundoff}\). Defining \(c\) as the variable that compensates for the lost low-order bits, we get \(c_{new} = c_{old} + (a - a_{eff})\).

Process

The Kahan summation algorithm primarily uses a separate variable to accumulate errors. As shown in the reference code below, \(sum\) is the final cumulative result to be returned. \(c\) is the variable that compensates for the lost low-order bits (the truncated part) and is a necessary variable in the Kahan summation algorithm.

Since \(sum\) is large and \(y\) is small, the low-order bits of \(y\) are lost. \((t - sum)\) cancels out the high-order part of \(y\), and subtracting \(y\) recovers the negative value (the low-order part of \(y\)). Therefore, algebraically, \(c\) is always zero. In the next iteration, the lost low-order part will be updated and added to \(y\).

Implementation

Reference Code

float kahanSum(vector<float> nums) {
  float sum = 0.0f;
  float c = 0.0f;
  for (auto num : nums) {
    float y = num - c;
    float t = sum + y;
    c = (t - sum) - y;
    sum = t;
  }
  return sum;
}

Exercises

In OI, Kahan summation mainly serves as an auxiliary tool to provide results with smaller errors.

Example Problem CodeForces Contest 800 Problem A. Voltage Keepsake

There are \(n\) devices used simultaneously. The \(i\)-th device consumes \(a_{i}\) units of power per second. This consumption is continuous. That is, in \(\lambda\) seconds, the device will consume \(\lambda \times a_{i}\) units of power. The \(i\)-th device currently stores \(b_{i}\) units of electricity. All devices can store any amount of power. There is a charger that can be plugged into any single device. The charger adds \(p\) units of power per second to the device. This charging is continuous. That is, if a device is plugged in for \(\lambda\) seconds, it will gain \(\lambda \times p\) units of power. We can switch which device is being charged at any time unit (including real numbers) (switching time is negligible). Find the maximum time these devices can be used before one of them reaches \(0\) units of power.

Example Problem CodeForces Contest 504 Problem B. Misha and Permutations Summation

Define the sum of two permutations \(p\) and \(q\) of the numbers \(0, 1, \cdots, (n - 1)\) as \(Perm((Ord(p)+Ord(q))\bmod n!)\), where \(Perm(x)\) is the \(x\)-th lexicographic permutation (counting from zero) of the numbers \(0, 1, \cdots, (n-1)\), and \(Ord(p)\) is the number of the lexicographic permutation \(p\). For example, \(Perm(0) = (0, 1, \cdots , n - 2, n - 1)\), \(Perm(n! - 1) = (n - 1, n-2,\cdots, 1,0))\). Misha has two permutations \(p\) and \(q\), find their sum.

Summation in Programming Languages

Python's standard library specifies the fsum function for exact rounded summation, which can be used to return an accurate floating-point sum of values in an iterable. It avoids loss of precision by tracking multiple intermediate partial sums using the Shewchuk algorithm.

In the Julia language, the default implementation of the sum function uses pairwise summation to achieve high accuracy and good performance. Meanwhile, the external library function sum_kbn provides an implementation of the Neumaier variant for situations requiring higher precision, as seen in KahanSummation.jl.

References and Notes

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用