4 ms·
> Floating point arithmetic is not arithmetic we learnt in school. This is certainly true ... > It's not commutative ... Hmm. Is it not commutative?
by ColinWright 14y ago
> Floating point arithmetic is not arithmetic we learnt in school.
This is certainly true ...
> It's not commutative ...
Hmm. Is it not commutative?
- sankha93 14y agoTake 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 agoBut 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 agoIn 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 agoThat'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.
- hartror 14y agoOrder of operations matter. Try adding a few small floating point numbers together with a really large floating point number in different orders.
- ColinWright 14y agoYes, that's associativity failing, not commutativity.
- lmm 14y agoIt's not commutative: -0 + 0 = -0, but 0 + -0 = 0.
- ColinWright 14y agoAh, that's news to me - can you provide a reference? I'm trying to look it up but my Google-fu is failing to find a specific link. Thanks.
- VMG 14y agoThis paper is referenced in a newsgroup discussion: http://dl.acm.org/citation.cfm?id=156301.156303 http://dl.acm.org/citation.cfm?id=156301.156303 http://newsgroups.derkeiler.com/Archive/Comp/comp.lang.functional/2007-05/msg00256.html http://newsgroups.derkeiler.com/Archive/Comp/comp.lang.funct...
- ColinWright 14y agoSo quoting from the discussion: Oh, of course: for non-NaNs, correctly implemented IEEE arithmetic is "exactly rounded". So addition of non-NaNs must be commutative for any given rounding rule, ...
- notaddicted 14y agoThat's not the behaviour I'm seeing on my machine. (http://codepad.org/rlLuB5VF http://codepad.org/rlLuB5VF) ... but, if you subtract zero from zero the sign depends on the order: http://codepad.org/g9LzZWPd http://codepad.org/g9LzZWPd .
- pascal_cuoq 14y ago(-0.) + (+0.) and (+0.) + (-0.) both evaluate to +0., as any compiler should readily confirm.
- T-hawk 14y agoIs the compiler calculating that at compile time based on the lexical tokens, or at runtime with native CPU floating point instructions? That absolutely matters.