Martin Ba - 1 year ago 92
C++ Question

# Inhowfar do IEEE754 floats satisfy LessThanComparable?

TL;DR Do the IEEE754 floating point values including

`NaN`
satisfy
`LessThanComparable`
?

Specifically, question "Why does Release/Debug have a different result for std::min?" got me looking up
`LessThanComparable`
:

The type must work with < operator and the result should have standard
semantics.

## Requirements

The type T satisfies LessThanComparable if

Given

• a, b, and c, expressions of type T or const T

The following expressions must be valid and have their specified
effects

Establishes strict weak ordering relation with the following properties
(...)

I double checked it in the standard and it seems it states basically the same there, and I looked at the Wikipedia def of strict weak ordering.

Some think that the set of IEEE floating point vales that includes NaN does not satisfy this concept: Any comparison with NaN on either side will always yield false, but I have been looking at the definitions, and it is not at all apparent to me whether the presence of
`NaN`
breaks strict weak ordering:

For the list given at Wikipedia:

• For all x in S, it is not the case that x < x (irreflexivity).

• For all x, y in S, if x < y then it is not the case that y < x (asymmetry).
`see below`

• For all x, y, z in S, if x < y and y < z then x < z (transitivity).

• For all x, y, z in S, if x is incomparable with y (neither x < y nor y < x hold), and y is incomparable with z, then x is incomparable with z (transitivity of incomparability).

It seems that the strict weak ordering axiom as defined on Wikipedia explicitly calls out possible
`incomparable`
values: NaN seems a good candidate here?

On the other hand, the standard says: (25.5/4)

If we define
`equiv(a, b)`
as
`!comp(a, b) && !comp(b, a)`
, then the
requirements are that comp and equiv both be transitive relations:

(4.1) —
`comp(a, b) && comp(b, c)`
implies
`comp(a, c)`

(4.2) —
`equiv(a, b) && equiv(b, c)`
implies
`equiv(a, c)`

With these definitions,
`equiv(x, NaN)`
is always
`true`
(because
`!comp(a, NaN)==true`
and
`!comp(Nan, a)==true`
: comparison with Nan yields false, negation then yields true)

But clearly (4.2) is not satisfied, e.g:

`````` equiv(3.0, NaN) && equiv(NaN, 7.0) **does not** imply equiv(3.0, 7.0)
``````

So is what the standard defines not a Strict Weak Ordering, or -- more likely indeed -- am I missing something here?

Strict weak ordering requires that strongly-ordered equivalence classes exist. This is not true of IEEE754.

The problem isn't that there exist multiple NaN values which are equivalent to each other, but that the entire class of NaNs is unordered with respect to the real line.

The violation of (4.2) causes the test in the fourth bullet point you quoted from Wikipedia to also fail (let `y` be a NaN).

For an example of incomparability that is allowed in a strict weak ordering, consider sign-magnitude integers. Then:

-4 < -3 < -2 < -1 < { -0, +0 } < +1 < +2 < +3 < +4

Neither `-0 < +0` nor `+0 < -0` is true, so the ordering is weak. But the class formed by these equivalent values is strongly ordered with respect to all others.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download