Is floating point addition commutative in C++?

Question

For floating point values, is it guaranteed that a + b is the same as¹ b + a?

I believe this is guaranteed in IEEE754, however the C++ standard does not specify that IEEE754 must be used. The only relevant text seems to be from [expr.add]#3:

The result of the binary + operator is the sum of the operands.

The mathematical operation "sum" is commutative. However, the mathematical operation "sum" is also associative, whereas floating point addition is definitely not associative. So, it seems to me that we cannot conclude that the commutativity of "sum" in mathematics means that this quote specifies commutativity in C++.

---

Footnote 1:
"Same" as in bitwise identical, like memcmp rather than ==, to distinguish +0 from -0. IEEE754 treats +0.0 == -0.0 as true, but also has specific rules for signed zero. +0 + -0 and -0 + +0 both produce +0 in IEEE754, same for addition of opposite-sign values with equal magnitude. An == that followed IEEE semantics would hide non-commutativity of signed-zero if that was the criterion.

Also, a+b == b+a is false with IEEE754 math if either input is NaN. memcmp will say whether two NaNs have the same bit-pattern (including payload), although we can consider NaN propagation rules separately from commutativity of valid math operations.

Urina

std::strtod("nan")+0.0 == 0.0+std::strtod("nan") is false. But I doubt that's what you mean. – Hilaryhilbert

Why limit yourself to floating-point? Without giving it too much thought, I don’t think that C++ requires integer addition be commutative either (e.g. overflow results could be non-commutative). – Thrombophlebitis

@StephenCanon: That would seem to depend on what treatment you feel like giving undefined behaviour. Integer addition is commutative for programs that don't elicit UB, and whether a program elicits UB cannot hinge on commutativity of integer addition. – Arawakan

Asking if a+b == b+a is not the same as asking if it's commutative, because == is different from memcmp. The most likely non-commutativity in a system similar to IEEE754, like some software-FP emulation, would probably be with signed-zero or different NaN payloads. (e.g. 0 + -0 might always take the sign of the left-hand operand, vs in IEEE754 always being +0.) But it might well still implement -0 == +0 IEEE semantics. (Also, a+b == b+a is false for IEEE754 if either a or b is NaN. Again, memcmp would actually check commutativity). – Claiborne

For builtin types, gcc will swap the operands of + without any particular precaution. – Xuthus

I understand that C++ is IEEE compliant (addition is commutative for not-NANs) unless you use --fast-math or -Ofast, in which anything can happen. – Richter

Answer 1

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.

Barry

You seem to be saying that a + b is unspecified then. Can you elaborate on this? It's normally stated that the reason the compiler is not allowed to optimize floating point operations is that it might change the observable behaviour of the program. However if the result of a + b can change between invocations , that would invalidate that line of reasoning. – Urina

@MattMcNabb It depends on which rules the compiler wants to follow. The C and C++ standards are very lenient, but because they are so lenient, an implementation may implement stricter rules (possibly conforming to other standards) and still conform to the C++ standard as well. Such stricter rules would indeed disallow many floating point optimisations. The C++ standard states in [expr.prim.general]p11: "The values of the floating operands and the results of floating expressions may be represented in greater precision and range than that required by the type; the types are not changed thereby." – Barry

@MattMcNabb What this means in practise is that, as an example, if a and b are of type double, and a + b is exactly representable in long double yet would require rounding in double, and the CPU only has a single floating-point type with the precision of long double, then you might get the result of (long double) a + (long double) b instead. Both the C and the C++ standards intentionally do not want to require the compiler to emit a round instruction after each and every single floating-point operation. – Barry

[conv.double] says that if a long double value is not exactly representable in double then the result is implementation-defined. (So it should give the same value each time). Does [conv.double] apply here? – Urina

@MattMcNabb That doesn't apply: there isn't any long double value. There is a double value with the precision of long double, and no actual conversion between different types. And implementation-defined doesn't mean it has to give the same value each time, it merely means the implementation has to document how it chooses the result: implementations may provide options to change the rounding mode at run time. – Barry

OK. Has there been discussion of this anywhere else (i.e. whether a + b == a + b can be false in C++)? Not that I distrust you or anything; but when the standard avoids specifically covering an issue, it can be insightful to see some discussion between opposing viewpoints. – Urina

There's GCC's bug 323, about a program that does assume that a + b == a + b, where the GCC developers have closed it as not a bug. – Barry

interesting point on that thread that this implies std::set<double> is broken – Urina

Correction: its status is actually suspended, not resolved. Regardless, it's a good read. – Barry

Worse than the fact that a+b == a+b isn't guaranteed, IEEE-754 requires that some values of a won't even satisfy a==a. – Woolridge

@Woolridge do you mean NaN and Inf with 'some values'? Or does it also hold for "real" numbers – Kielce

@KamiKaze: I was referring to NaN. While it's possible to write a NaN-safe floating-point sort that behaves sensibly by using an initial pass to partition the data into NaN and everything else, and then sorting the part that doesn't contain any NaN values, that's an extra layer of complexity that could have been avoided by defining a relational operator that works consistently. – Woolridge

@Woolridge I would say a false evaluation of NaN is quite sensible, because it arises under circumstances that really are an "error" and they should not be compared. – Kielce

@KamiKaze: If one is trying to e.g. identify all the unique values in a list, cache a pure function's inputs and outputs, compare old and new copies of a list, etc., having NaN compare unequal to itself is decidedly unhelpful. Equivalence relations and pure functions are useful concepts--if f() is a pure function, and code knows that that x==y, and f(x) is z, code that needs f(y) can substitute f(x). If == operates as an equivalence relation, code can handle NaN like any other value. Otherwise special handling will be needed to avoid having every request for f(NaN) add a new entry.. – Woolridge

...to the table (which will never match anything and may as well not exist). – Woolridge

A small addition to "It is not even required that a + b == a + b": it is not even required that "two different literals with the same mathematical value, such as 1.23 and 1.230, convert to the same value" (source). – Waterbuck

Answer 2

No, the C++ language generally wouldn't make such a requirement of the hardware. Only the associativity of operators is defined.

All kinds of crazy things do happen in floating-point arithmetic. Perhaps, on some machine, adding zero to an denormal number produces zero. Conceivable that a machine could avoid updating memory in the case of adding a zero-valued register to a denormal in memory. Possible that a really dumb compiler would always put the LHS in memory and the RHS in a register.

Note, though, that a machine with non-commutative addition would need to specifically define how expressions map to instructions, if you're going to have any control over which operation you get. Does the left-hand side go into the first machine operand or the second?

Such an ABI specification, mentioning the construction of expressions and instructions in the same breath, would be quite pathological.

Service

Operator associativity is different from the mathematical property of associativity of multiplication. The former says that double x = a * b * c; will be evaluated in a left-associative manner as (a * b) * c. In math, associativity means that (a * b) * c == a * (b * c). Floating point addition/multipliation is evaluated left-associative, but is definitely not mathematically associative (i.e. a right-associative evaluation could give a different result). – Morphinism

@Morphinism Hmm, I don't see how that relates to the question or my answer. This discussion is entirely about notation used for programming floating-point calculations, not the mathematical operations which are being approximated. – Service

I simply pointed out that associativity has two meanings and it wasn't clear from the context which one you were referring to. – Morphinism

Answer 3

The C++ standard very specifically does not guarantee IEEE 754. The library does have some support for IEC 559 (which is basically just the IEC's version of the IEEE 754 standard), so you can check whether the underlying implementation uses IEEE 754/IEC 559 though (and when it does, you can depend on what it guarantees, of course).

For the most part, the C and C++ standards assume that such basic operations will be implemented however the underlying hardware works. For something as common as IEEE 754, they'll let you detect whether it's present, but still don't require it.

Lachman

I've accepted hvd's answer (for now at least) - assuming it to be correct, it indicates that even on IEEE754 implementations , if the result is not exactly representable then we do not even have identity, let alone commutativity. – Urina

Answer 4

Addition at any given precision is commutative except for NaN payloads, for a C++ implementation using IEEE FP math.

Marc Glisse comments:

For builtin types, gcc will swap the operands of + without any particular precaution.

---

• Finite inputs with non-zero results are the simple case, obviously commutative. Addition is one of the "basic" FP math operations so IEEE754 requires the result to be "correctly rounded" (rounding error <= 0.5 ulp), so there's only one possible numerical result, and only one bit-pattern that represents it.

  Non-IEEE FP math may allow larger rounding errors (e.g. allowing off-by-one in the LSB of the mantissa, so rounding error <= 1 ulp). It could conceivably be non-commutative with the final result depending on which operand is which. I think most people would consider this a bad design, but C++ probably doesn't forbid it.

• If the result is zero (finite inputs with same magnitudes but opposite signs), it's always +0.0 in IEEE math. (Or -0.0 in the roundTowardNegative rounding mode). This rule covers the case of +0 + (-0.0) and the reverse both producing +0.0. See What is (+0)+(-0) by IEEE floating point standard?

  Inputs with different magnitudes can't underflow to zero, unless you have subnormal inputs for an FPU operating in flush-to-zero mode (subnormal outputs are rounded toward zero). In that case you can get -0.0 as a result if the exact result was negative. But it's still commutative.

• Addition can produce -0.0 from -0 + -0, which is trivially commutative because both inputs are the same value.

• -Inf + anything finite is -Inf. +Inf + anything finite is +Inf. +Inf + -Inf is NaN. Neither of these depends on order.

• NaN + anything or anything + NaN is NaN. "payload" (mantissa) of the NaN depends on the FPU. IIRC, keeping the payload of the previous NaN.

• NaN + NaN produces NaN. If I recall, nothing specifies which NaN payload is kept, or if a new payload could be invented. Hardly anyone does anything with NaN payloads to track where they came from, so this is not a big deal.

Both inputs to + in C++ will be promoted to matching types. Specifically to the wider of the two input types if they don't already match. So there's no asymmetry of types.

---

For a+b == b+a on its own, that can be false for NaNs because of IEEE == semantics (not because of + semantics), same as a+b == a+b.

With strict FP math (no extra precision kept between C statements, e.g. gcc -ffloat-store if using legacy x87 math on x86), I think that equality is equivalent to !isunordered(a,b) which tests if either of them are NaN.

Otherwise it's possible that a compiler could CSE with earlier code for one but not the other and have one of them evaluated with higher-precision values of a and b. (Strict ISO C++ requires that high-precision temporaries only exist within expressions even for FLT_EVAL_METHOD==2 (like x87), not across statements, but gcc by default doesn't respect that. Only with g++ -std=c++03 or whatever instead of gnu++20, or with -ffloat-store for x87 specifically.)

On a C++ implementation with FLT_EVAL_METHOD == 0 (no extra precision for temporaries within an expression), this source of optimization differences wouldn't be a factor.

Claiborne