Hacker News new | ask | show | jobs
by dbaupp 3902 days 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-p... [2]: http://www-2.cs.cmu.edu/afs/cs/project/quake/public/papers/r...