A long sum can lose increments even when every input is represented exactly. The previous unit separates rounding error from the sensitivity of the sum itself. Here we examine one algorithm that remembers part of the rounding from an addition and feeds it into the next one.
A correction with a sign
Definition 1.4.1
(Compensated (Kahan) summation)
For represented inputs , start with and . At each step compute, in the displayed order,
Return . The assignment to uses the old .
In exact arithmetic and the correction would be zero. With rounding, estimates the increment actually absorbed, so estimates the excess of absorbed over intended increment. The next step subtracts this excess. Each operation above is separately rounded; the estimate is not generally the exact error.
Common mistake
(Simplifying the correction to zero)
Reassociating the expression algebraically to zero would destroy the calculation, because the algebra holds only in exact arithmetic. Implementations, and compilers that reorder floating-point operations, must preserve the stated evaluation order.
Proposition 1.4.2
(Exact arithmetic gives zero correction)
If every operation is carried out exactly, then after each step and after step .
Proof
(Induction over the steps)
Suppose and before step . Then , , , so the new is , and . The claim holds before the first step, since .
Proof X-ray
What is being corrected?
Imagine, only for intuition, that and were exact and the only error were the rounded addition . If , then and the next input is adjusted by . In the actual algorithm both subtractions are rounded too: this argument explains the sign but is not a proof that all errors are removed or an error bound.
Ten increments in a small decimal machine
Worked example 1.4.3
(Ten ones added to 1000)
Use decimal arithmetic with three significant digits, rounding each operation to nearest with ties to even, and assume exponent range is wide enough. All inputs in are exactly representable; their exact sum is . After processing , both ordinary and compensated sums are with . At this scale adjacent representable numbers above are ten apart.
| Number of ones processed | Ordinary sum | Compensated | Correction |
|---|---|---|---|
| 1 | |||
| 4 | |||
| 5 | |||
| 6 | |||
| 10 |
At the fifth one, is exactly halfway and ties-to-even selects ; at the sixth, and rounds to . The correction is then . The following four inputs reduce to zero. The ordinary sum loses every one; this compensated result happens to be exact. A different format, rounding rule or order can change the trace.
Worked example 1.4.4
(Two increments of four)
In the same machine process , whose exact sum is . Ordinary summation gives and again : the result is , which is from the exact sum. For the compensated method, after we have . The first gives , , . The second gives , , , so , only from the exact sum. In every row of the two traces, equals the exact partial sum (for example and ). That identity is an observation about these traces, valid while and the subtractions in are exact; the counterexample below shows where it fails.
Worked example 1.4.5
(When nothing is rounded)
Process in the same machine. Every intermediate quantity has at most three significant digits: ; then ; then . The returned sum is , the correction stays zero, and the method agrees with ordinary summation, as the proposition on exact arithmetic predicts.
Counterexample mode
Compensation is not an exact accumulator
In the same decimal machine, process . After the first two inputs . At the third, , so the returned sum is , although the exact sum of the represented inputs is . The correction itself can be rounded away when it is combined with a much larger input.
What the method does and does not promise
The algorithm uses a constant number of arithmetic operations and storage locations per input, so costs operations and working storage, excluding the input. It can substantially improve a sum, but this example-driven explanation is not a universal error bound.
Common mistake
(Expecting compensation to cure ill-conditioning)
Cancellation can make the exact sum sensitive to perturbations of the data; compensation cannot recover digits absent from the represented inputs. It improves the arithmetic, not the conditioning of the problem.
Overflow, underflow, nonfinite numbers and compiler reassociation require separate analysis. For applications requiring certified error, choose an error analysis and arithmetic model appropriate to the implementation.
Exercises
Quick check
(After the third one in the ten-increment example, find .)
Follow the pattern of the first rows of the table.
Solution · Answer
: the third step has , and .
Quick check
(Why is the sixth correction positive?)
Compare the absorbed increment with the intended one.
Solution · Answer
The rounded step absorbs when the intended adjusted increment is , leaving excess .
Quick check
(After the seventh one in the ten-increment example, find .)
Start from after the sixth.
Solution · Answer
, , and . So .
Quick check
(Does the final counterexample establish that every compensated sum fails?)
Count how many inputs and which arithmetic it uses.
Solution · Answer
No; it shows one failure under the stated arithmetic and order, not typical or universal behavior.