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

user_16759116 0
Viewed 339

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).

floating-accuracy ieee-754 floating-point math
2 Answers

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.

user_9363100

If you have N floats you have N! possible sequences how to add them. Assuming you always do one addition at a time this leads to 0.5[N*(N-1)]*(N-2)! versions of the calculation. (assuming a+b=b+a for the first pair and a+b has the same rounding as b+a). After each step there is a rounding error. As long as you dont force the calculation sequence I would expect N!/2 possible results due to rounding errors. The differences however should be in the lowest significant digits as long as you work with pure positive numbers.

If you do things like substracting very similar numbers (example:9999999.9+(-9999999.8) the rounding errors can become critcal however (depending on the size of your floats).

Using brackets you can get even more combinations (Example: (a+b)+(c+d) may differ from ((a+b)+c)+d because you force a rounding with each pair of brackets.

user_116546200
Related