Wikipedia example of floating point non-associativity

Factual Questions
1

I can’t figure out whether I just don’t understand the following example from the Wikipedia page on floating point about the non-associativity of some FP operations, or if it is in error.

Here’s the page (the example is in the second shaded box below the page ref):
Accuracy Problems

Here’s the full example:
While floating-point addition and multiplication are both commutative (a + b = b + a and a×b = b×a), they are not necessarily associative. That is, (a + b) + c is not necessarily equal to a + (b + c). Using 7-digit decimal arithmetic:



 1234.567 + 45.67844 = 1280.245
                       1280.245 + 0.0004 = 1280.245
 but 
 45.67840 + 0.00004 = 45.67844
                      45.67844 + 1234.567 = 1280.246

Huh? I can’t tell what a, b, and c are supposed to be in the example.
My first guess was a=1234.567, b=45.67804, c=0.0004, but that doesn’t work for the second part of the problem.

Even so, the first part (1234.567 + 45.67844 = 1280.245) doesn’t even jibe with the last part (45.67844 + 1234.567 = 1280.246).

The only thing I can think of is that I don’t understand “7-digit decimal arithmetic,” but if that’s the case, I can’t for the life of me figure out what that means.

:confused:

2

I agree their example seems wrong. Think of it this way

1234567 + .1 + .1 + .1 + …= 1234567 no matter how many times you repeat adding .1. However it you add 10 .1s together first you get 1 then add that to 1234567 you get 1234568.

3

a=0.00004
b=45.67840
c=1234.567

4

I think that you’re correct on a = 1234.567, b = 45.67804, and c= 0.0004. The first expression is thus:
a + b = X
… X + c = Y – (Note I’m using li’t dots because I can’t get the spacing to line up)

The second expression is:
b + c = Z
… Z + a = W not equal to Y.

They’ve taken the fact that the floating point addition is associative, so they’re actually saying:
(a + b) + c not equal (b + c) + a.

Seems a confusing way to put it.

5

The problem with floating point is that it is not precise. Some numbers can not be accurately represented as a floating point number.

When you add multiple numbers and use intermediate results, the specific combinations of numbers that get added together make a difference because some will end up with intermediate results that are accurately represented and some will not thus introducing small errors.

6

Well, if that’s the case, then in the first expression, they mistakenly calculate (c + (b + a)) + a. That is, in the first expression, they add the 0.0004 twice.

I think they did just genuinely mess up when writing it.

7

Also, they switch from 0.0004 to 0.00004. And they say in one instance that 1234.567 + 45.67844 = 1280.245, while in another instance that 45.67844 + 1234.567 = 1280.246, violating the very commutativity they allege. All kinds of problems. They seem to have just fucked up all around.

Of course, it should be replaced with a better, clearer example. Which one of us will surely soon provide…

8

Thanks for the ideas. At least I’m not crazy for thinking the example is screwed up. Cheers.

9

The difference is the number of decimal places and rounding.

NOTE: The numbers didn’t match between the examples, so I fixed them.



a = 1234.567
b =   45.67844
c =    0.00004

In the first example, since the first number only has 3 decimal places (.567), you round off the answer to match, so (.245). You lose the (.xxx44) from the second number.



  1234.567
+   45.67844
____________
  1280.24544   rounds to   1280.245

For the next step, you again round off the answer to the smallest number of decimal places, so it’s still (.245). The (0.0004) gets lost, just like (.xxx44) in the first addition.



  1280.245
+    0.00004
____________
  1280.24504   rounds to   1280.245

In the second example, you’re first adding together the numbers with extra decimal places. This time, because they both have 5 digits after the decimal, that (.00004) adds with the (.xxxx4) to make (.xxxx8).



  45.67844
+  0.00004
____________
  45.67848

So that in the next step, when you round off the number to the match decimal places, the (.24548) rounds up to (.246) instead of the (.245) you got before.



    45.67848 
+ 1234.567
____________
  1280.24548   rounds to   1280.246

I hope that all makes sense, and that I got the numbers and math right. Is there a mathematical equivalent to Gaudere’s law, or does G.L. cover math too?

10

But (.24548) rounds down to (.245).

The example works correctly if you use c = 0.0004 instead of 0.00004. Then you get (.24584), which does round up.

ETA:

One of those, apparently. :wink:

11

Bah! That doesn’t work either.

[crosses fingers]Try 1234.567 + 45.67834 + 0.0004

12

OldGuy already gave a fine example. Associativity is often phrased in the particular 3-ary case, but this actually suffices to ensure (and is thus equivalent to saying) that one can arbitrarily re-parenthesize any string of the operation. But, clearly, using 7 digits of precision, (…((1234567 + 0.1) + 0.1) … + 0.1) = 1234567, no matter how many 0.1s you use, while 1234567 + ((…(0.1 + 0.1) + …) + 0.1), with ten 0.1s, is equal to 1234567 + 1 = 1234568. Thus, associativity fails.

We can pull from this a specific three-ary instance of associativity’s failure, if you like. Assuming the digit 5 is the first point at which we switch to rounding up, then (1234567 + 0.1) + 0.4 = 1234567 + 0.4 = 1234567, while 1234567 + (0.1 + 0.4) = 1234567 + 0.5 = 1234568. There; quick and easy failure of ternary associativity.

13

Great! I’ve made the changes to the Wikipedia page, basically using redtail23’s example with ZenBeam’s minor correction. Here’s the latest version:


 a = 1234.567, b = 45.67834, c = 0.0004
 
 (a + b) + c:
     1234.567   (a)
   +   45.67834 (b)
   ____________
     1280.24534   rounds to   1280.245
 
    1280.245  (a + b)
   +   0.0004 (c)
   ____________
    1280.2454   rounds to   1280.245  <--- (a + b) + c
 
 a + (b + c):
   45.67834 (b)
 +  0.0004  (c)
 ____________
   45.67874
 
     45.67874 (b + c)
 + 1234.567   (a)
 ____________
   1280.24574   rounds to   1280.246 <--- a + (b + c)

Thanks again (and I hope we made Wikipedia a little bit better).

14

It’s even easier if you use negative numbers:

1 + (1E99 + -1E99)

vs.

(1 + 1E99) + -1E99

I’m just saying …