AIOJ

Introduction

The Kahan summation algorithm, also known as compensated summation or carried summation, is an algorithm used to reduce the error when accumulating a sequence of floating-point values with finite precision. It works mainly by maintaining a separate variable to accumulate the error (commonly named $c$ ).

William Kahan primarily developed the algorithm in the 1960s. Because Ivo Babuška independently proposed a similar algorithm, Kahan summation is also known as Kahan–Babuška summation.

Rounding error

In computer programs, real numbers must be represented approximately with a finite number of digits. Today, most computers use the floating-point representation specified by IEEE-754 for this purpose. For $\frac{1}{3}$ , we cannot represent the value exactly with finitely many digits, so some value must be rounded (truncated) when IEEE-754 representation is used. This rounding error is a characteristic of floating-point computation.

Floating-point addition is commutative but not associative. In other words, $a+b = b+a$ , but $(a+b)+c \neq a+(b+c)$ . Thus, when adding a sequence of floating-point values, we may either accumulate them one by one from left to right or pair them according to their original order. The second method is relatively slower and requires more memory; it is also used by some specialized summation functions in programming languages, and generally produces more accurate results.

To obtain a more accurate floating-point sum, we use the Kahan summation algorithm.

When computing $S_{new}=S_{old}+a$ (where $a$ is one value in the floating-point sequence), define the value actually added to $S$ as $a_{eff}=S_{new}-S_{old}$ . If $a_{eff}$ is greater than $a$ , there is an upward rounding error; if $a_{eff}$ is less than $a$ , there is a downward rounding error. Define the rounding error as $E_{roundoff} = a_{eff} - a$ . The value used to correct this rounding error is $a-a_{eff}$ , namely the negative of $E_{roundoff}$ . If $c$ denotes the variable that compensates for lost low-order bits, we obtain $c_{new} = c_{old} + (a - a_{eff})$ .

Process

The Kahan summation algorithm mainly uses a separate variable to accumulate error. In the reference code below, $sum$ is the final accumulated result. $c$ compensates for lost low-order bits (the part that was discarded), and is essential to Kahan summation.

Because $sum$ is large and $y$ is small, the low-order bits of $y$ are lost. $(t - sum)$ cancels the high-order part of $y$ , and subtracting $y$ restores the negative value (the low-order part of $y$ ). Therefore, in exact arithmetic, $c$ is always zero. In the next iteration, the lost low-order part is 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 that provides a value with a smaller numerical error.

Example CodeForces Contest 800 Problem A. Voltage Keepsake

There are $n$ devices operating simultaneously. Device $i$ consumes $a_{i}$ units of power per second, continuously; that is, over $\lambda$ seconds it consumes $\lambda \times a_{i}$ units of power. Device $i$ currently stores $b_{i}$ units of energy, and every device can store any amount of energy. There is a charger that can be connected to any one device. It supplies $p$ units of energy per second, continuously; that is, a device connected for $\lambda$ seconds receives $\lambda \times p$ units of energy. We may switch the device being charged at any time, including a real-valued time, and switching takes no time. Find the longest time for which the devices can be used before one of them reaches $0$ units of power.

Example CodeForces Contest 504 Problem B. Misha and Permutations Summation

For the numbers $0, 1, \cdots, (n - 1)$ , define the sum of two permutations $p$ and $q$ as $Perm((Ord(p)+Ord(q))\bmod n!)$ , where $Perm(x)$ is the $0, 1, \cdots, (n-1)$ -th lexicographic permutation of the numbers $x$ , counted from zero, and $Ord(p)$ is the lexicographic rank of permutation $p$ . For example, $Perm(0) = (0, 1, \cdots , n - 2, n - 1)$ and $Perm(n! - 1) = (n - 1, n-2,\cdots, 1,0))$ . Given two permutations $p$ and $q$ , find their sum.

Summation in programming languages

Python's standard library provides the fsum function for accurately rounded floating-point summation of values in an iterable. It avoids loss of precision by tracking multiple partial sums using the Shewchuk algorithm.

In Julia, the default implementation of the sum function uses pairwise summation to obtain high precision and good performance. The external library function sum_kbn provides a Neumaier-variant implementation for cases requiring higher precision; see KahanSummation.jl for details.