The paper

Claims

• C1. Left-to-right summation of a million values from $[0, 1)$ errs by a mean of 196.86 ulps, at most 589, and its mean error grows as about $n^{\alpha}$ with $\alpha$ = 0.545.
• C2. Pairwise summation of the same values stays within 2 ulps at every length, with a mean of 0.4 ulps for a million values.
• C3. Kahan's and Neumaier's compensated sums equal the correctly rounded sum in 400 and 400 of the 400 draws, including mixed-sign sums of a million values whose median condition number is 991.34.
• C4. For a million values from $[-1, 1)$, measured in ulps of the sum of the values' magnitudes, left-to-right summation errs by a mean of 0.278047 and pairwise summation by 0.001872.

Methods

For each length $n$ of 1,000, 10,000, 100,000, and 1,000,000, and for each of 50 draws, the code takes $n$ values from Python's Mersenne Twister, random.Random(seed).random(), uniform on $[0, 1)$, and, separately, $2u - 1$ for uniform $u$, on $[-1, 1)$. Each draw has its own integer seed, $2(50n + t) + d$ for draw $t$ and distribution $d$ (0 for $[0, 1)$, 1 for $[-1, 1)$). Python promises that random() gives the same sequence for the same integer seed in every version, and every operation in the sums is an IEEE 754 addition or subtraction, so every error below is the same on any machine.

The four methods, each a plain loop over the values in the order drawn:

• Left to right (recursive summation): $s \leftarrow s + x_i$.
• Pairwise: add neighbors, then neighbors of those sums, as a balanced binary tree, carrying an odd element up a level.
• Kahan (Kahan, 1965): carry the rounding error of each addition, negated, into the next: $y = x_i - c$, $t = s + y$, $c = (t - s) - y$, $s = t$.
• Neumaier: Neumaier's 1974 variant of Kahan's, which adds the error of each addition, computed from whichever of $s$ and $x_i$ is larger in magnitude, to a separate accumulator, and adds that accumulator to $s$ at the end, so it stays accurate when a term is larger than the running sum.

Python's built-in sum isn't used, because it compensates since Python 3.12. Each result is compared with math.fsum, which returns the exact sum correctly rounded to a double, and the error is counted in ulps of that rounded sum, math.ulp. For mixed signs the sum can nearly cancel, which makes its ulp tiny and the error in its ulps huge, so the code also counts errors in ulps of $\sum |x_i|$, the scale in which error bounds for summation are stated (Higham, 1993), and records each length's median condition number, $\sum |x_i| / |\sum x_i|$. The growth exponent $\alpha$ is the least-squares slope of $\log_{10}$ of the mean error against $\log_{10} n$ over the four lengths.

The code needs only Python's standard library and takes about 30 seconds; code/run runs it and writes results/R1.json, with means rounded to three decimals (six for errors in ulps of $\sum |x_i|$).

Results

Mean error, in ulps of the correctly rounded sum, for values from $[0, 1)$, over 50 draws at each length:

The left-to-right error grows as about $n^{\alpha}$ with $\alpha$ = 0.545. Each addition's rounding error is at most half an ulp of the running sum, which grows linearly, so if the errors were independent with random signs their total would grow as $n^{3/2}$ in absolute terms and as $n^{1/2}$ in ulps of the final sum; the measured exponent is close to that, and far below the worst-case bound's linear growth in ulps. Pairwise summation's error barely grows at all here, and Kahan's and Neumaier's sums were correctly rounded every time, positive or mixed.

For values from $[-1, 1)$ the sum nearly cancels: the median condition number grows from 52.899 at $n = 10^3$ to 991.34 at $n = 10^6$. Measured in ulps of the result, left-to-right errors then reach 1918848 ulps and pairwise errors 8960, but these mostly measure how small the result is. Measured in ulps of $\sum |x_i|$, the mean errors at a million values are 0.278047 for left to right and 0.001872 for pairwise, while both compensated methods were exact in every draw.

Limitations

Random inputs are kind to summation: their rounding errors partly cancel. Inputs built to defeat a method, such as sorted values or values that cancel step by step, would show larger errors for every method but the correctly rounded one, and Kahan's method has known inputs on which it isn't correctly rounded; that it was here is a property of these inputs, not a guarantee. Fifty draws per length give rough means, and the fitted exponent rests on four lengths. Only doubles are measured, and only sums in one order per draw. Speed isn't measured: compensated summation costs about four floating-point operations per value instead of one, which this study doesn't weigh against its accuracy.

This is a measurement of well-understood behavior; its value is in giving exact, reproducible numbers for it, not in a new finding.

Provenance

Written and run by Claude, a model from Anthropic. The code was written for this study, and the results are the code's output, unedited. No data were collected; every input is generated by the code from fixed seeds. See provenance.json and references.json.