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

Transarctic

Comments are not for extended discussion; this conversation has been moved to chat. – Eulogy

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.

Stoeber

Did you use any particular method for generating those examples and causing catastrophic cancellation? If you know of any reasonably principled way of sampling such lists, that would be very helpful for testing your conjecture about the existence of lists such that 'all different permutations would produce different sums modulo commutativity for large enough n', which I believe to be false for n>3. – Britska

I used an SMT solver (z3 in particular), which can handle floating-point logics. (smtlib.cs.uiowa.edu/theories-FloatingPoint.shtml) Regarding the conjecture: You might very well be right, and while an SMT solver can be used to find such examples for any given concrete n, it's hard to use them to answer the query for an arbitrary (symbolic) n. (Also, SMT solvers slow down significantly with more symbolic values around.) A proper numeric analysis is called for, which is beyond my current skill set. – Stoeber

I've never used an SMT solver, so I'll have to check that out. Since Python's float64 supposedly allows subnormal numbers, I suspect that Sterbenz' lemma puts a much stronger limit on how many permutations can give unique sums than commutativity. Commutativity should only cut permutations in half, however, as stated in the post comments, it's unclear whether a 4-variable example with more than 9 (out of 12 possible) distinct sums exists, while there are many examples with exactly 9. – Britska

@Britska For whatever it's worth, I used an SMT solver to search for such a combination: i.e., 4 doubles with 10 different sums. SMT based search did not produce a result in about 2 hours of run time. This doesn't mean there's no such case, but rather the search space is too big for the solver to handle in 2 hours. As solvers improve one might get a result in the future, but I wouldn't hold my breath for a standard SMT-solver to come up with such answers with ease. – Stoeber

That's quite interesting; is there any way you can share your code so I can study your method? I'm trying to compose an answer to this question and tried a basic hill-climbing approach, but the discontinuous nature of the search space (what is a small perturbation of a float?) makes that very difficult. I can say with fairly high confidence that f(4) is 9, f(5) is 31 and f(6) is 125 or 126; however there may be pathological examples that are singularities/extremely discontinuous and can't easily be found by optimization techniques. – Britska

@Britska SMT solvers are usually programmed from higher-level languages, and I've used the SBV library in Haskell to code this one up, which allows scripting z3 from Haskell. Not sure how useful this will be to you, but here's the whole program: gist.github.com/LeventErkok/75d0c0bad4a4415ca26d0a5a7eda95af A similar program can be written in C/C++/Java/Python etc., as well, though I find Haskell to be quite concise and much easier to use. I'm happy to further collaborate on this if you'd like to pursue the idea. – Stoeber

@Britska With "what is a small perturbation of a float?" do you mean how to find some? I'm using math.nextafter now. – Transarctic

Answer 2

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.

Entomologize