How many different sums can we get from very few floats?

Question

Someone just asked why sum(myfloats) differed from sum(reversed(myfloats)). Quickly got duped to Is floating point math broken? and deleted.

But it made me curious: How many different sums can we get from very few floats, just by summing them in different orders? With three floats, we can get three different sums:

>>> from itertools import permutations
>>> for perm in permutations([0.2, 0.3, 0.4]):
        print(perm, sum(perm))

(0.2, 0.3, 0.4) 0.9
(0.2, 0.4, 0.3) 0.9000000000000001
(0.3, 0.2, 0.4) 0.9
(0.3, 0.4, 0.2) 0.8999999999999999
(0.4, 0.2, 0.3) 0.9000000000000001
(0.4, 0.3, 0.2) 0.8999999999999999

I believe addition is commutative (i.e., a + b == b + a) for floats. And we have three choices for the first pair to add and then one "choice" for the second add, so three sums is the most we can get with just three values.

Can we get more than three different sums with four values? With some experiments I didn't find such a case. If we can't: why not? If we can: how many? How many with five?

As Eric just pointed out, for more than three values there are also different possibilities than just summing left to right, for example (a+b) + (c+d). I'm interested in any way to add the numbers.

Note I'm talking about 64-bit floats (I'm a Python guy, I know in other languages they're often called doubles).

Answer 1

You most certainly can. For your specific question:

Can we get more than three different sums with four values?

Here's one set of values to show this is indeed the case:

v0 = -1.5426605224883486e63
v1 =  7.199082438280276e62
v2 =  8.227522786603223e62
v3 = -1.4272476927059597e45

print (v0 + v2 + v1 + v3)
print (v3 + v1 + v0 + v2)
print (v2 + v1 + v0 + v3)
print (v1 + v2 + v3 + v0)

When I run this, I get:

1.36873053731e+48
1.370157785e+48
1.46007438964e+48
1.46150163733e+48

all of which are different.

With 5, here's an example set:

v0 = -8.016918059381093e-292
v1 =                    -0.0
v2 = 2.4463434328110855e-296
v3 =  8.016673425037811e-292
v4 =   1.73833895195875e-310

print(v4 + v1 + v0 + v2 + v3)
print(v2 + v3 + v0 + v1 + v4)
print(v4 + v3 + v1 + v0 + v2)
print(v1 + v0 + v2 + v3 + v4)
print(v1 + v4 + v2 + v0 + v3)

This prints:

-8.90029543403e-308
1.73833895196e-310
-4.45041933248e-308
-8.88291204451e-308
0.0

again, with all different outcomes.

I wouldn't be surprised if you could find values with n values for any sufficiently large n (perhaps n>2 is enough) such that all different permutations would produce different sums; modulo those that are equivalent due to commutativity. (Though of course this is a conjecture.) With catastrophic cancelation, you can arrange for the outcome to differ largely.