Hacker News new | past | comments | ask | show | jobs | submit login

This is a good thing to be aware of.

Also the "field" of floating point numbers is not commutative†, (can run on JS console:)

x=0;for (let i=0; i<10000; i++) { x+=0.0000000000000000001; }; x+=1

--> 1.000000000000001

x=1;for (let i=0; i<10000; i++) { x+=0.0000000000000000001; };

--> 1

Although most of the time a+b===b+a can be relied on. And for most of the stuff we do on the web it's fine!††

† edit: Please s/commutative/associative/, thanks for the comments below.

†† edit: that's wrong! Replace with (a+b)+c === a+(b+c)






Note that the addition is commutative [1], i.e. a+b==b+a always.

What is failing is associativity, i.e. (a+b)+c==a+(b+c)

For example

(.0000000000000001 + .0000000000000001 ) + 1.0

--> 1.0000000000000002

.0000000000000001 + (.0000000000000001 + 1.0)

--> 1.0

In your example, you are mixing both properties,

(.0000000000000001 + .0000000000000001) + 1.0

--> 1.0000000000000002

(1.0 + .0000000000000001) + .0000000000000001

--> 1.0

but the difference is caused by the lack of associativity, not by the lack of commutativity.

[1] Perhaps you must exclude -0.0. I think it is commutative even with -0.0, but I'm never 100% sure.


I tried to determine how to perform IEEE 754 addition (in order to see whether it's commutative) by reading the standard: https://sci-hub.tw/10.1109/IEEESTD.2019.8766229

(Well, it's a big document. I searched for the string "addition", which occurs just 41 times.)

I failed, but I believe I can show that the standard requires addition to be commutative in all cases:

1. "Clause 5 of this standard specifies the result of a single arithmetic operation." (§10.1)

2. "All conforming implementations of this standard shall provide the operations listed in this clause for all supported arithmetic formats, except as stated below. Unless otherwise specified, each of the computational operations specified by this standard that returns a numeric result shall be performed as if it first produced an intermediate result correct to infinite precision and with unbounded range, and then rounded that intermediate result, if necessary, to fit in the destination’s format" (§5.1)

Obviously, addition of real numbers is commutative, so the intermediate result produced for addition(a,b) must be equal to that produced for addition(b,a). I hope, but cannot guarantee, that the rounding applied to that intermediate result would not then depend on the order of operands provided to the addition operator.

3. "The operation addition(x, y) computes x+y. The preferred exponent is min(Q(x), Q(y))." (§5.4.1). This is the entire definition of addition, as far as I could find. (It's also defined, just above this statement, as being a general-computational operation. According to §5.1, a general-computational operation is one which produces floating-point or integer results, rounds all results according to §4, and might signal floating-point exceptions according to §7.)

4. The standard encourages programming language implementations to treat IEEE 754 addition as commutative (§10.4):

> A language implementation preserves the literal meaning of the source code by, for example:

> - Applying the properties of real numbers to floating-point expressions only when they preserve numerical results and flags raised:

> -- Applying the commutative law only to operations, such as addition and multiplication, for which neither the numerical values of the results, nor the representations of the results, depend on the order of the operands.

> -- Applying the associative or distributive laws only when they preserve numerical results and flags raised.

> -- Applying the identity laws (0 + x and 1 × x) only when they preserve numerical results and flags raised.

This looks like a guarantee that, in IEEE 754 addition, "the representation of the result" (i.e. the sign/exponent/significand triple, or a special infinite or NaN value - §3.2) does not "depend on the order of the operands". §3.2 specifically allows an implementation to map multiple bitstrings ("encodings") to a single "representation", so it's possible that the bit pattern of the result of an addition may differ depending on the order of the addends.

5. "Except for the quantize operation, the value of a floating-point result (and hence its cohort) is determined by the operation and the operands’ values; it is never dependent on the representation or encoding of an operand."

"The selection of a particular representation for a floating-point result is dependent on the operands’ representations, as described below, but is not affected by their encoding." (both from §5.2)

HOWEVER...

6. §6, dealing with infinite and NaN values, implicitly contemplates that there might be a distinction between addition(a,b) and addition(b,a):

> Operations on infinite operands are usually exact and therefore signal no exceptions, including, among others,

> - addition(∞, x), addition(x, ∞), subtraction(∞, x), or subtraction(x, ∞), for finite x (§6.1)


> Also the "field" of floating point numbers is not commutative, (can run on JS console:)

OK.

    >> x = 0;
       0
    >> for (let i=0; i<10000; i++) { x+=0.0000000000000000001; };
       1.0000000000000924e-15
    >> x + 1
       1.000000000000001
    >> 1 + x
       1.000000000000001

You've identified a problem, but it isn't that addition is noncommutative.

Yeah, what is demonstrated here is that floating point addition is nonassociative.

Your example shows that floating-point addition isn't associative, not that it isn't commutative.

Isn't that more of an associativity problem than a commutativity problem, though?

1.0 + 1e-16 == 1e-16 + 1.0 == 1.0 as well as 1.0 + 1e-15 == 1e-15 + 1.0 == 1.000000000000001

however (1.0 + (1e-16 + 1e-16)) == 1.0 + 2e-16 == 1.0000000000000002, whereas ((1.0 + 1e-16) + 1e-16) == 1.0 + 1e-16 == 1.0


Yep. The TL;DR of a numerical analysis class I took is that if you're going to sum a list of floats, sort it by increasing numeric value first so that the tiny values aren't rounded to zero every time.

Really? It wasn't to use Kahan summation?

https://en.wikipedia.org/wiki/Kahan_summation_algorithm


Hah! Well, yeah, that too. But if there's a gun to your head, sorting the list before adding will get you most of the way there with the least amount of work.



Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: