Accurate summation algorithm

A point I’ve made several times previously is the following:

  • Mathematically, since + is associative and commutative, all correct summation algorithms are algebraically equivalent to each other, in particular they are all equivalent to left-to-right summation.

  • The -ffast-math option gives the compiler license to transform any algorithm into any algebraically equivalent one in the mathematical sense.

  • Therefore -ffast-math gives the compiler license to transform any summation algorithm into any other summation algorithm, including left-to-right summation.

That’s why there’s no fundamentally useful answer to this question: the only thing you can find out is how a particular compiler happens to optimize your code. A different compiler in -ffast-math mode or a different version of your own compiler – or the exact same compiler targeting a different architecture – can always make the situation different and potentially much worse. The example above happens to outsmart one particular compiler, but as @mbauman’s post shows, a slightly smarter compiler could straightforwardly overcome that obstacle and make this exact same code fail. Or put another way, there are no reliable summation algorithms in -ffast-math mode.

The same argument applies to superaccumulators in principle, but they typically operate on floating-point values reinterpreted as integers which -ffast-math gives no additional license to optimize, so they should be safe enough. They’re much slower than approximate summation algorithms, however.