Pairwise summation, the trick NumPy uses for nearly free accuracy

Question

A plain accumulation loop has worst-case rounding error that grows like $O(n\varepsilon)$ : the more numbers you add, the worse it gets. Kahan summation fixes this but costs about four extra operations per element. There is a middle path that costs almost nothing.

Implement pairwise (divide-and-conquer) summation, state its error bound, and explain why it is nearly as fast as the naive loop.

Accepted Answer

Instead of folding every value into one running total, split the array in half, sum each half recursively, and add the two halves. The recursion balances the additions into a tree of depth \log2 n, so any single value passes through only about \log2 n roundings instead of up to n of them. The worst-case error drops from O(n\varepsilon) to O(\varepsilon \log n). The base-case cutoff (here 128) is the key to speed: below it, a straight loop runs at full cache-friendly, branch-predictable speed, and the recursion only kicks in for the coarse structure. So the overhead versus a naive loop is a ha…

Pairwise summation, the trick NumPy uses for nearly free accuracy

Your answer

More Coding questions