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.

Jarvey

Couldn't "NaN shenanigans" be just "sheNaNigans"? – Isis

Note that your signaling NaN gets normalized to a quiet NaN on actual calculations if you don't enable exceptions. – Leia

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.

Terceira

But this is not by language definition, right? The standard says "The value representation of floating-point types is implementation-defined." So this is only true for when e.g. IEEE754 is used. If there's no NaN, it is different? – Weathercock

Yep, this is only addressing the case where std::numeric_limits<float>::is_iec559 == true or otherwise has_infinity == has_quiet_NaN == true – Terceira

... although arguably since that's a legal implementation, it's sufficient to demonstrate you can't rely on min<float> forming a monoid in general. It doesn't prevent it forming a monoid on some particular implementation (presumably without a quiet NaN). – Terceira