Is Floating-Point Addition and Multiplication Associative

Is floating-point addition and multiplication associative?

Floating point addition is not necessarily associative. If you change the order in which you add things up, this can change the result.

The standard paper on the subject is What Every Computer Scientist Should Know about Floating Point Arithmetic. It gives the following example:

Another grey area concerns the interpretation of parentheses. Due to roundoff errors, the associative laws of algebra do not necessarily hold for floating-point numbers. For example, the expression (x+y)+z has a totally different answer than x+(y+z) when x = 1e30, y = -1e30 and z = 1 (it is 1 in the former case, 0 in the latter).

Are floating point operations in C associative?

The compiler is not allowed to perform "optimizations", which would result in a different value computed, than the one computed according to abstract machine semantics.

5.1.2.3 Program execution

[#1] The semantic descriptions in this International
Standard describe the behavior of an abstract machine in
which issues of optimization are irrelevant.

[#3] In the abstract machine, all expressions are evaluated
as specified by the semantics.

[#13] EXAMPLE 5 Rearrangement for floating-point expressions
is often restricted because of limitations in precision as
well as range. The implementation cannot generally apply
the mathematical associative rules for addition or
multiplication, nor the distributive rule, because of
roundoff error, even in the absence of overflow and
underflow.

In your example:

(a + b) + c

or even without the parentheses:

a + b + c

we have

   +
  / \
  +  c
 / \
 a  b

and the compiler is required to generate code as if a is summed with b and the result is summed with c.

Example of non associative floating point addition

There is no such example, because floating point addition, as defined by IEEE-754, is guaranteed to be commutative. The relevant verbiage:

...Each of the operations shall be performed as if it first produced an intermediate result correct to infinite precision and with unbounded range, and then coerced this intermediate result to fit in the destination's format.

That is, the addition itself is performed with infinite precision; all errors in the result come from the need to discard some of that precision. Since infinite-precision (that is, "regular") addition is commutative, that means the operation as a whole is commutative.

What you may be thinking of is associativity. Floating point addition is not associative, because the precision loss following adding the first two numbers will not generally be the same as that from adding the last two numbers. The most common example of this is known as "catastrophic cancellation": (1 + 1e100) + -1e100 = 0, and 1 + (1e100 + -1e100) = 1.

Is floating point addition commutative in C++?

It is not even required that a + b == a + b. One of the subexpressions may hold the result of the addition with more precision than the other one, for example when the use of multiple additions requires one of the subexpressions to be temporarily stored in memory, when the other subexpression can be kept in a register (with higher precision).

If a + b == a + b is not guaranteed, a + b == b + a cannot be guaranteed. If a + b does not have to return the same value each time, and the values are different, one of them necessarily will not be equal to one particular evaluation of b + a.

When does (b - a) + a != b exactly in floating point

To extend my comment, I tested small fractions up to a limit n, i.e.
a_i = i/n, i=1..n and b_j = j/n, j=i+1..n. It seems that for roughly 4 .. 5 percent of the test cases the equality failed. Here some numbers:

   n   failed    tested     f/t
  10        2        55    0.036
  50       48      1275    0.038
 100      204      5050    0.040
 127      383      8128    0.047
2047   114752   2096128    0.055

The failed cases for n=10 are a=2/10, b=9/10 and a=3/10, b=9/10.

Is floating-point multiplication commutative?

According to Wikipedia, yes, float multiplication is commutative.

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

Is arithmetic commutative and associative?

Assuming no unchecked overflows occur, .NET's integer addition and multiplication (int, long, etc.) is commutative and associative, like the real numbers in math. Floating point arithmetic (float and double) is commutative, but not always precisely associative, due to the limits of precision. From Wikipedia (with an example in the article):

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

Here's an example:

a: 0.825402526103613
b: 0.909231618470155
c: 0.654626872695343
(a*b)*c: 0.491285733573819
a*(b*c): 0.49128573357382

There are some examples where the results appear the same when turned into a string, but are different ((a*b)*c != a*(b*c) is true, and (a*b)*c - a*(b*c) returns a small value, not 0).

a: 0.613781429181705
b: 0.648859122604532
c: 0.795545351596337
(a*b)*c: 0.316832045751117
a*(b*c): 0.316832045751117
difference: 5.55111512312578E-17

---

Related Topics