You sum 100 million P&L increments of order 0.01 into a double running total that reaches 1e7. Estimate the error of naive left-to-right summation, then compare pairwise summation and Kahan compensated summation on error and on cost.

You sum 100 million P&L increments of order 0.01 into a double running total that reaches 1e7. Estimate the error of naive left-to-right summation, then compare pairwise summation and Kahan compensated summation on error and on cost.

Approach: Model each addition as introducing a relative rounding error on the running total, then ask how those errors accumulate over n additions under each scheme.

Naive summation accumulates an error growing like n times epsilon times the running total, which for n of 1e8, epsilon of 2.2e-16 and a total of 1e7 is on the order of 0.2, so the last two digits of the P&L are wrong; pairwise summation reduces the growth to log n times epsilon, about 1e-7 here at essentially the same cost, and Kahan summation reduces it to a constant times epsilon, about 2e-9, for three extra operations per element. Once the total reaches 1e7 the spacing between doubles is about 2e-9, so part of each 0.01 increment is rounded away and the loss repeats every step, which is why the rounding error accumulation scales with n. Pairwise summation is what a careful library does by default and needs only a small stack of partial sums. Kahan keeps a compensation term holding the part lost in the previous addition and adds it back, and it must not be compiled with fast math, which deletes the compensation as algebraically zero.

Follow-up: What does summing in a different thread order do to reproducibility, and how would you make the total deterministic across thread counts?

Key concepts: rounding error accumulation, pairwise summation, kahan summation, epsilon.