Identity element for std::min/float monoid

Question

In this (very interesting) talk the speaker poses a question:

What is the e value for the float/std::min monoid.

In other words: what is the identity element for the monoid composed of standard C++ floats and std::min operation? The speaker says that the answer is "interesting".

I think that std::numeric_limits<float>::infinity() should be the answer, as evidenced by the code:

  const auto max = numeric_limits<float>::max();
  const auto min = numeric_limits<float>::min();
  const auto nan = numeric_limits<float>::signaling_NaN();
  const auto nan2 = numeric_limits<float>::quiet_NaN();
  const auto inf = numeric_limits<float>::infinity();
  const auto minus_inf = -inf;
  cout << std::min(max, inf) << "\n";
  cout << std::min(min, inf) << "\n";
  cout << std::min(nan, inf) << "\n";
  cout << std::min(nan2, inf) << "\n";
  cout << std::min(inf, inf) << "\n";
  cout << std::min(minus_inf, inf) << "\n";

Which prints:

3.40282e+38
1.17549e-38
nan
nan
inf
-inf

We always get the left argument when calling std::min in the tests. Is infinity the correct answer or am I missing something?

EDIT: I seemed to have missed something. This:

  cout << std::min(nan, inf) << "\n";
  cout << std::min(inf, nan) << "\n";

prints:

nan
inf

So we get different answers based on the order of arguments in case of NaN shenanigans.

Answer 1

It's obviously true that min on the affinely-extended reals (ie, including +/-inf but excluding NaN) is a monoid.

However, the result of comparing anything to NaN is not false, but "unordered". This implies that < is only a partial order on float, and std::min<float> (which is defined in terms of <) is therefore not a monoid.

There is in IEEE 754 a totalOrder predicate - although I don't know how it is exposed in C++, if at all. We could write our own min in terms of this instead of <, and that would form a monoid ... but it wouldn't be std::min.

---

For confirmation, we can compile a variant of your code on godbolt, to see how this is implemented in practice:

• the comparison is done with comiss, which has the possible results

    UNORDERED: ZF,PF,CF←111;
    GREATER_THAN: ZF,PF,CF←000;
    LESS_THAN: ZF,PF,CF←001;
    EQUAL: ZF,PF,CF←100;
  

  and specifies that

  The unordered result is returned if either source operand is a NaN (QNaN or SNaN).

• the branch is done with jbe, which will

  Jump short if below or equal (CF=1 or ZF=1).

You can see that the UNORDERED result is actually treated as both less than and equal by this conditional branch.

So, assuming this is a legal model of the unordered comparison mentioned by IEEE 754, it should be permissible to have both

min(min(+inf, NaN), -inf) =
min(+inf, -inf)           = -inf

and

min(+inf, min(NaN, -inf)) =
min(+inf, NaN)            = +inf

which means min<float> is not associative and is therefore not a monoid.