When Kahan summation still fails, and Neumaier's fix

Question

Classic Kahan summation cancels the drift when many small numbers pile onto a growing total. But feed it a big number, then a small one, then the big number's negative:

>>> kahan_sum([1e16, 1.0, -1e16])
0.0        # the 1.0 vanished; the true answer is 1.0

Explain why classic Kahan loses the 1.0 here, and implement a variant that returns 1.0.

Accepted Answer

Kahan's compensation register c captures the low bits lost when a small addend is added to a large running total. It quietly assumes the running total is the bigger of the two operands. When the incoming value x is larger in magnitude than total, the roundoff lands in the bits of total, not x, and the term (t - total) - y measures the wrong quantity. Tracing [1e16, 1.0, -1e16]: after adding 1e16 then 1.0, the sum rounds back to 1e16 (numbers near 1e16 are spaced 2 apart, so 1e16 + 1 rounds to 1e16); Kahan records the lost 1.0 in c, but the final += -1e16 step overwrites the bookkeeping and th…

When Kahan summation still fails, and Neumaier's fix

Your answer

More Coding questions