Pairwise summation

Remarks

The recursion has depth $\lceil \log_2 n \rceil$, and each term $x_i$ takes part in at most $\lceil \log_2 n \rceil$ floating-point additions. Each addition multiplies the term by a factor $1 + \delta$ with $\abs{\delta} \le u$, so $\hat s = \sum x_i (1 + \theta_i)$ with $\abs{\theta_i} \le \gamma_{\lceil \log_2 n \rceil}$, which gives the bound. For $n = 10^6$ terms in double precision, the bound is about $20u \sum \abs{x_i}$, against about $10^6 u \sum \abs{x_i}$ for plain recursive summation. The cost is the same $n - 1$ additions as recursive summation. In practice the recursion stops at blocks of moderate size that are summed in a simple loop, which gives a bound of order $(B + \log_2 n) u \sum \abs{x_i}$ for blocks of size $B$.

Going deeper

For a student

The error bound grows like $u \log_2 n$, against $u n$ for recursive summation. The Kahan summation algorithm does better still, with a leading term $2u$ independent of $n$, at about four times the cost. Pairwise summation is the default in several numerical libraries because it costs no extra arithmetic. The same divide-and-conquer pattern appears in the fast Fourier transform, whose rounding errors also grow only logarithmically. For random rounding errors the typical error is even smaller, of order $u \sqrt{\log n}$ in a statistical model.