[ars]

Why would it fail in the edge case?

A double has 15 digits of precision. Even if the 16th digit of all 50 numbers is 9, it still would not be enough to affect the 11th digit of the sum.

If all the numbers were solid 9's then you would worry about the loss of precision from adding many small numbers to a large one, but with just 50 inputs at worst you loose 3 digits of precision, which is still not enough to affect the 11th digit.

[Someone]

A simple edge case:

  10000000000...0000000000
  10000000000...0000000000
  10000000000...0000000000
  10000000000...0000000001
  19999999999...9999999999

Only 5 numbers, but you need all digits even to compute the first digit of the sum. There are many less obvious edge cases; any set of numbers that adds up to

  60000000000...0000000000

with at least one carry from the last column will do.

[ars]

When you store 19999999999...9999999999 as a float you round it, not truncate it.

19999999999...9999999999 = 20.....00 when rounded to 15 significant digits.

You can even truncate it to 15 digits just to get it in there, and then round it to 14 digits.

[extension]

Rounding can just as easily give you the wrong answer as truncating e.g:

  100000...000000
  199999...999999

[ars]

Good point.

Hmm, I guess I would split the numbers in half, and sum each set of half's (making sure to set the exponent correctly).

Then add the less significant half to the more significant half.

i.e. basically add the numbers in order of magnitude. It doesn't have to be just two half's.

Did anyone post this as a solution?

I do remember learning this somewhere - it was a warning about loss of precision when adding lots of small numbers to a few large ones. And the solution was to do all the small numbers first.

Seems like this would be a perfect place to teach this lesson. Do you know if this site does that?