3 ms·

If the list is known in advance, what about a strategy of sorting the items by absolute value and then summing from smallest to largest? Would this improve acc

• dbaupp 11y ago
  That will ensure that, say, 1e20 + 1 + 1 + ... + 1 (with 1e20 ones) is correctly computed as 2e20 (edit: this isn't actually true: it just gets a bit closer to 2e20, something like 1e20+1e16), but it can still result in catastrophic cancellation, e.g. [1, 1e20, -1e20] should sum to 1, but will give 0, despite already being sorted. Something like the msum of [1] is needed to get a (provably[2]) exact summation. [1]: http://code.activestate.com/recipes/393090-binary-floating-point-summation-accurate-to-full-p/ http://code.activestate.com/recipes/393090-binary-floating-p... [2]: http://www-2.cs.cmu.edu/afs/cs/project/quake/public/papers/robust-arithmetic.ps http://www-2.cs.cmu.edu/afs/cs/project/quake/public/papers/r...