The sum that cannot be wrong

Four essays of measurement have established that a reduction’s answer is a function of how the work was divided. This one is about the repair, which exists, is not exotic, and is nearly a hundred years old in one of its two forms.

The test first, because the claim it settles is a bitwise claim and deserves a bitwise test.

Five policies. Three of them return hundreds of answers and two of them return one. There is no tolerance anywhere in that measurement, and there cannot be: reproducible to 10⁻¹² is a phrase about accuracy wearing the wrong word, and every policy on the figure satisfies it.

Why a compensated sum is not the answer #

The first row worth reading is the third. Kahan’s compensated summation carries the part of each addend the running total could not hold and puts it back on the next step; it is the standard repair for summation error and the order they are added in measures what it recovers. Here it returns 119 distinct answers over four hundred permutations against a plain loop’s 303, and is not reproducible. The ratio between those two counts is not the size of what compensation buys — the section on sample size below has the number that is — but the one and the three hundred are the whole of what the census asks.

The mechanism is exactly the one in where the disagreement comes from. Compensation removes most of each rounding, and what is left is still committed at the running total’s scale and still depends on the order the terms arrived in. A better answer is still an answer that depends on the order.

And compensation is nearly reproducible at mild conditioning, which is how it earns its reputation.

Compensation goes from six answers to a hundred and twenty between κ = 10² and 10⁴, and the two reproducible policies never move. Across κ = 10², 10⁴, 10⁶, 10⁸ and 10¹⁰ the compensated count runs 6, 122, 117, 119 and 122 while pre-rounded and exact return 1 at every one of the five.

So a compensated loop is reproducible on the problems where reproducibility is not in question and not on the others, which is precisely the shape that makes a repair hard to distrust. A developer who reaches for compensation after two machines disagree is very likely working at κ = 10⁴ or worse — that is why the machines disagreed — and will get 122 answers where the plain loop gave 316. Two thirds fewer, still not one. Meanwhile the same census at κ = 10² would have shown compensation returning six and looked like a fix.

The plain loop’s own count saturates too, at 316, 290, 303, 310 across the last four conditionings: once nearly every permutation gives a different answer there is nowhere further to go, and 400 permutations of 400 would be the ceiling. Both curves flatten, which means the ratio between them — the number a reader would quote as what compensation buys — is a property of the sample size rather than of the conditioning past κ = 10⁴.

This is the single most useful thing in the field for anybody who has reached for a compensated loop after seeing two machines disagree. It will help. It will help by twenty in the spread of the answers and by four orders in the error — and it will not make the two machines agree, and no amount of further compensation will, because accuracy is not what the problem is.

Snapping to a common multiple #

The policy that does work is one idea, and the idea is small enough to state completely.

Choose a spacing δ — a power of two, taken from the largest term. Replace each xᵢ by the nearest multiple of δ. Then:

• every partial sum of multiples of δ is itself a multiple of δ;
• a multiple of δ smaller than 2⁵³δ is exactly representable in binary64;
• so every addition in the reduction is exact, whatever order they happen in;
• so the answer is a function of the multiset, and two machines that agree about δ agree about the answer, bit for bit.

That is the whole algorithm. Three operations an element — a divide by δ, a round, an add — and the only thing the two machines have to share is δ, which is computed from max|xᵢ| and is therefore a function of the data as well.

What is given up is stated rather than hidden. Each addend moves by at most δ/2, so the answer is wrong by at most nδ/2. With δ = 2^(E−40) where 2^E is the largest term, and 1,024 terms, that is about 10⁻¹⁰ of the largest term. The measured error on the census vector is 2.3·10⁻⁷ relative to the answer — which is four orders worse than the ordinary reduction it replaces.

It is the reproducible policy and the less accurate one, at the same time. That pair of properties is not a defect of this algorithm; it is the shape of the whole trade, and accuracy and agreement are different properties is the essay that takes it apart.

The width is the knob, and it has a refusal #

The one parameter is w, the number of bits below the top exponent that δ sits at. It decides both halves of the trade.

Larger w means a finer δ, a smaller error, and less headroom in the accumulator. The accumulator has to hold a sum of n multiples of δ without rounding, which needs w + log₂n bits below the top exponent — and binary64 has 53. So the condition is

w + log₂ n < 53,

and it is not advice: it is asserted inside the routine, and a caller who asks for w = 48 on 4,096 terms is refused rather than quietly given an answer that is neither accurate nor reproducible. That refusal is one of the sixteen this field runs whenever the figure is drawn, and it is the one that would otherwise be a silent failure — an overflowing accumulator rounds, a rounded partial sum is not a multiple of δ, and the order starts mattering again with nothing to indicate it.

At w = 40 and 4,096 terms the condition is 40 + 12 = 52 < 53, with one bit to spare. That is the default and it is close to the edge on purpose: the whole value of the policy is the accuracy it retains, and the accuracy is 2⁻ʷ.

The second pass, which recovers the accuracy #

The obvious repair to a policy that rounds every addend is to look at what it discarded.

Subtract the snapped values from the originals; the residues are small, so a δ computed from their largest element is far finer; snap and sum those too. The second sum is exact for the same reason the first was, so the total is still order-independent, and the error is now the residue of a residue.

Measured on the census vector: the one-pass answer is wrong by 2.3·10⁻⁷ and the two-pass answer is exactly the correctly rounded sum — an error of zero, not merely a small one. That is a stronger result than the algorithm guarantees in general, and the honest reading is that this vector’s residues fit comfortably inside the second accumulator rather than that two passes are always exact. What the algorithm does guarantee is that the second pass costs seven operations an element instead of three and leaves the reproducibility untouched.

Seven operations an element, order-independent, and as accurate as anything on the figure. If this field has one recommendation, that is it.

The other reproducible policy, and why it is not the recommendation #

Exact accumulation is the older and simpler idea: carry enough of the sum that no information is lost, and round once at the end. Kulisch’s superaccumulator is a fixed-point register wide enough for every binary64 product; Shewchuk’s expansion, which is what this site uses for ground truth throughout, carries a list of non-overlapping partials and needs no special hardware.

Its output is the correctly rounded sum, which is a function of the multiset by definition, so it is order-independent for free. It is the right answer in the strongest sense available, and it is what every figure in this field is measured against.

It costs about twelve operations an element and forty words of state on this site’s measurement, against three and one, and the state is the part that decides the matter. Three operations and one accumulator is a loop that vectorises; twelve operations and a list is a loop that does not. On a reduction that is memory-bound — which is most of them, and which is the whole subject of where the flop count stopped predicting the time — the pre-rounded policy is nearly free and the exact one is not.

So the ordering is: exact accumulation when the answer matters more than the cost, two-pass pre-rounding when both matter, and one-pass pre-rounding when a reproducible answer of modest accuracy is what is wanted. What determinism costs draws all six policies on one figure with the numbers on them.

What “reproducible” is a claim about, exactly #

Three qualifications, because the word is doing a lot of work and it is easy to over-claim.

It is reproducible across orderings, not across everything. Two machines that agree about δ agree about the answer. δ is computed from max|xᵢ|, so two machines that see the same data agree about δ — but a machine that receives the data in a different partition still computes the same max, since a maximum is order-independent. That is why the policy composes with a parallel reduction at all, and it is the one detail of the algorithm that has to be got right.

It is not reproducible across precisions. Change the format and δ changes, and everything moves. Nothing in this field claims otherwise, and no policy could: a binary32 sum and a binary64 sum are different computations.

And it is not a statement about the rest of the program. A reproducible reduction inside an algorithm with an ordinary reduction somewhere else buys nothing. What the field’s later essays measure is that the reductions that matter are few and identifiable — the two inner products in a conjugate gradient step, the one that computes a residual norm, the one behind a rank threshold — so this is a targeted repair rather than a rewrite.

Why the default is not this #

Both algorithms are published, neither is difficult, and no library computes a sum this way unless asked. That is worth explaining rather than complaining about, because the reason is a good one.

A reduction is usually memory-bound: the loop reads a number and adds it, and the add is free compared with the read. Three operations an element is therefore nearly free provided the loop still vectorises and still uses one accumulator per lane, and the pre-rounded loop does. Twelve operations and a list of partials does not, so exact accumulation is a real cost rather than a nominal one.

But the deeper reason is the one this whole field is about. The reproducible policy is slower on the axis every library is tuned against and its benefit does not appear in any measurement anybody takes. A benchmark reports time and, at best, accuracy against a reference; the quantity these policies buy — that the next run returns the same bits — is not in either column. A default is chosen by what is measured, and this is not measured.

The practical version of that observation is the one to act on. If a reduction’s answer feeds a comparison, the reproducible policy has to be asked for, in the same way an accurate one does, and knowing which reductions those are is what the vector that hides it is for: the sums at κ = 1 do not need it and the sums at κ = 10¹⁵ are the ones a verdict is read from.

Checking one reduction in place #

The test in this essay’s hero figure is four lines and transfers directly, which makes it the most portable thing in the field.

Sample permutations and require bitwise equality. Not a tolerance — the identity operator. Four hundred is plenty; the failure this catches is not rare, and a policy that fails does so on the second permutation rather than the four hundredth.

Then sample partition counts, which is a different test. A sum that is order-independent is partition-independent as well, but the reverse is not true — a routine can be pinned to one thread count and still be at the mercy of a scheduler, which is the distinction the open dots in the same program, twice are drawn to make.

And report κ of the vector when the test fails, because a failure at κ = 1 is a bug in the routine and a failure at κ = 10¹⁰ is the arithmetic behaving exactly as a bound every answer satisfies says it will. The two need different responses and the test cannot tell them apart on its own.

The test is the interesting half #

A closing note about how any of this is checked, because the test is more portable than the algorithm.

The claim this sum does not depend on the order is a claim about a set of 1,024! orderings, and no test visits them. What the site does instead is sample four hundred permutations from a seeded generator and require bitwise equality of every answer. Four hundred is not 1,024!, and the test is therefore evidence rather than proof — but it is evidence of exactly the right kind, because a policy that failed for one ordering in a thousand would show up as two distinct values rather than one, and a policy that fails for a single adversarial ordering is not what anybody is worried about.

Four hundred is plenty for the test and not for the bar #

The sentence above is about detection and it is comfortably true. Every failing policy on the figure shows its second distinct value on the second permutation: the plain loop, the eight-piece reduction and the compensated loop all fail at trial two, so four hundred is four hundred times more than the yes-or-no question needs.

The bars are a different quantity. They are the size of a set, and a set can only grow, so the number drawn is a function of how many permutations were tried. Running the same census to four thousand:

policy              at 100    at 400    at 4,000
one accumulator        95       303       1,426
eight pieces           27        72         149
compensated            57       119         404
pre-rounded             1         1           1
exact                   1         1           1

Nothing has converged except the ones at one. And the comparison the essay draws from those bars — compensation is three times better than a plain loop — is a statement about four hundred trials: at a hundred it is 1.7 times better and at four thousand it is 3.5.

The quantity that does converge is the spread, measured in units of the answer’s own ulp, because a range over a bounded distribution settles where a count over an unbounded one does not. From four hundred to four thousand:

policy              spread at 400    spread at 4,000    drift
one accumulator       1.01·10⁸ ulps     1.19·10⁸ ulps    +17%
eight pieces          4.46·10⁷          5.56·10⁷         +25%
compensated           4.92·10⁶          5.90·10⁶         +20%

Twenty per cent against factors of two to five. And it ranks the policies differently: by spread, compensation is twenty times better than the plain loop, not three — 1.19·10⁸ ulps against 5.9·10⁶ — which is the honest size of what compensation buys and is much larger than the bars suggest.

So the figure’s bar is the right thing to draw and the wrong thing to compare with. A count of one against a count of anything else is the entire content of the census, and it is exact, permanent and independent of the sweep. A count of 303 against a count of 119 is two samples of two growing sets, and the sentence to write beside them is both scatter and neither is reproducible, with the size of the scatter read off the spread.

That is the second time this collection has caught the same shape — the same correction applies to the four ratios drawn from seven runs — and both times the statistic was chosen because it is the one a figure can show.

The comparison being bitwise is what makes it a test at all. Written with a tolerance of 10⁻¹² it would pass for every policy on the figure including the plain loop, and would have measured nothing. This site’s habit is that an assertion which has never rejected anything proves nothing; the tolerance-free version of this one rejects the plain loop, the eight-piece reduction and the compensated loop, which is three of the five.

What the two policies have in common #

Both work by removing the arithmetic’s freedom rather than by improving its accuracy, and that is the sentence to carry out of the essay.

An ordinary reduction has a choice at every step: it rounds, and what it rounds to depends on what it has accumulated. Pre-rounding takes the choice away by making every intermediate exactly representable. Exact accumulation takes it away by keeping everything, so there is nothing to choose between. Neither of them is a cleverer rounding; both are the removal of rounding from the interior of the loop, with the single unavoidable rounding pushed to the end where the order cannot reach it.

That is why compensated summation — which is a cleverer rounding — cannot get there from where it stands, and why the 119 answers in the hero figure are not a failure of the compensation but a statement about what compensation is. The site has met this shape before: orthogonal is a number turns an adjective into a measurement by refusing to accept the adjective, and this refuses to accept accurate as an answer to a question about agreement.