3 ms·

Take the example that I cited: 1 + 2^-25 + 2^-25 ... (2^25 times) will give you 1. But if you do: 2^-25 + 2^-25 ... (2^25 times) + 1 it will give you 2.

ColinWright 14y ago
But that uses associativity, and it's the associativity that fails. I believe that "a+b" is always equal to "b+a". A more simplified version of what you say is that: 1 + x + x + x + x != x + x + x + x + 1 when x is suitably small. But to convert one into the other requires both associativity and commutativity: (((1 + x) + x) + x) + x -> (((x + 1) + x) + x) + x using commutativity -> ((x + (1 + x)) + x) + x using associativity -> ((x + (x + 1)) + x) + x using commutativity -> (((x + x) + 1) + x) + x using associativity -> ((x + x) + (1 + x)) + x using associativity -> ((x + x) + (x + 1)) + x using commutativity -> (((x + x) + x) + 1) + x using associativity -> ((x + x) + x) + (1 + x) using associativity -> ((x + x) + x) + (x + 1) using commutativity -> (((x + x) + x) + x) + 1 using associativity If you write Y as x+x+x+x, then 1+Y == Y+1. It's the associativity that fails.
- dankoss 14y ago
  In this example, yes. But floating point commutativity isn't guaranteed for multiple operations. a + b = b + a, but a * b * c is not guaranteed to equal b * a * c due to the rounding effects in the registers, which means commutativity fails for numbers that are at the rounding edges of floating point dynamic range.
  - ColinWright 14y ago
    That's a useful detail, but can you be a bit more specific, or point me to a paper that describes this effect in more detail? The discussions I've had in the past, and the papers I've read in the past, have left me with the impression that every "odd" effect of this type was an interaction with associativity, and not with commutativity. I'd like to learn more, but searches are failing to turn up anything specific and detailed. In particular, the usual reference - http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.ht... - doesn't seem to mention commutativity. Thanks.
  - pascal_cuoq 14y ago
    (a * b) * c is equal to (b * a) * c. And floating-point arithmetic is commutative, according to Eric Lippert (http://blogs.msdn.com/b/ericlippert/archive/2005/01/20/fun-with-floating-point-arithmetic-part-five.aspx http://blogs.msdn.com/b/ericlippert/archive/2005/01/20/fun-w... ) and an university professor (http://www.cs.uiuc.edu/class/fa07/cs498mjg/notes/floating-point.pdf http://www.cs.uiuc.edu/class/fa07/cs498mjg/notes/floating-po... ). Also according to IEEE 754, which I can't seem to find online.

ColinWright 14y ago

But that uses associativity, and it's the associativity that fails. I believe that "a+b" is always equal to "b+a". A more simplified version of what you say is that: 1 + x + x + x + x != x + x + x + x + 1 when x is suitably small. But to convert one into the other requires both associativity and commutativity: (((1 + x) + x) + x) + x -> (((x + 1) + x) + x) + x using commutativity -> ((x + (1 + x)) + x) + x using associativity -> ((x + (x + 1)) + x) + x using commutativity -> (((x + x) + 1) + x) + x using associativity -> ((x + x) + (1 + x)) + x using associativity -> ((x + x) + (x + 1)) + x using commutativity -> (((x + x) + x) + 1) + x using associativity -> ((x + x) + x) + (1 + x) using associativity -> ((x + x) + x) + (x + 1) using commutativity -> (((x + x) + x) + x) + 1 using associativity If you write Y as x+x+x+x, then 1+Y == Y+1. It's the associativity that fails.

dankoss 14y ago
In this example, yes. But floating point commutativity isn't guaranteed for multiple operations. a + b = b + a, but a * b * c is not guaranteed to equal b * a * c due to the rounding effects in the registers, which means commutativity fails for numbers that are at the rounding edges of floating point dynamic range.
- ColinWright 14y ago
  That's a useful detail, but can you be a bit more specific, or point me to a paper that describes this effect in more detail? The discussions I've had in the past, and the papers I've read in the past, have left me with the impression that every "odd" effect of this type was an interaction with associativity, and not with commutativity. I'd like to learn more, but searches are failing to turn up anything specific and detailed. In particular, the usual reference - http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.ht... - doesn't seem to mention commutativity. Thanks.
- pascal_cuoq 14y ago
  (a * b) * c is equal to (b * a) * c. And floating-point arithmetic is commutative, according to Eric Lippert (http://blogs.msdn.com/b/ericlippert/archive/2005/01/20/fun-with-floating-point-arithmetic-part-five.aspx http://blogs.msdn.com/b/ericlippert/archive/2005/01/20/fun-w... ) and an university professor (http://www.cs.uiuc.edu/class/fa07/cs498mjg/notes/floating-point.pdf http://www.cs.uiuc.edu/class/fa07/cs498mjg/notes/floating-po... ). Also according to IEEE 754, which I can't seem to find online.