std::max and NAN

[Mycroft Holmes]

hi,

does the standard say anything about the behaviour of std::min/max does on
(say, double) NAN?
we noticed that typical implementations of F(a,b), where F is either max or
min, is like:

(1) if (a COMPARISON b)
(2) return one of the arguments;
else
(3) return the other;

such an implementation breaks the obvious property F(a,b)==F(b,a)
in fact F(x,NAN) != F(NAN,x) because in both cases the comparison (1) is
false.

also it should hold that "min(a,b) LESS-OR-EQUAL max(a,b)"
where LESS-OR-EQUAL is a relaxed comparison operator so that NAN is
LESS-OR-EQUAL to NAN.

but again, this axiom is easily broken: the following implementation
(which -I think- is implemented in VC8 stl)

min(a,b) := a<b ? a : b
max(a,b) := a<b ? b : a

violates it, as min(x,NAN)==NAN, but max(x,NAN)==x

In other words, my question is: do max/min have to be consistent when one or
both arguments are NAN(s) or they are allowed to return an arbitrary result?

thanks in advance for the answer
-MH

[Ulrich Eckhardt]

Post by Mycroft Holmes
does the standard say anything about the behaviour of std::min/max does on
(say, double) NAN?

I don't know the standard, but looking at the documentation for the STL, it
mentions that '<' for max/min must provide a partial ordering, which
floating point numbers that are NAN simply break.

Post by Mycroft Holmes
we noticed that typical implementations of F(a,b), where F is either max
(1) if (a COMPARISON b)
(2) return one of the arguments;
else
(3) return the other;
such an implementation breaks the obvious property F(a,b)==F(b,a)
in fact F(x,NAN) != F(NAN,x) because in both cases the comparison (1) is
false.

I guess that you will find more such problems if you try to sort sequences
containing NAN.

Post by Mycroft Holmes
In other words, my question is: do max/min have to be consistent when one
or both arguments are NAN(s) or they are allowed to return an arbitrary
result?

I guess the behaviour is undefined, unless the standard changes the
requirements from the STL.

Uli

[Mycroft Holmes]

Post by Ulrich Eckhardt

Post by Mycroft Holmes
does the standard say anything about the behaviour of std::min/max does on
(say, double) NAN?

I don't know the standard, but looking at the documentation for the STL, it
mentions that '<' for max/min must provide a partial ordering, which
floating point numbers that are NAN simply break.

MSDN mentions that max/min return the first element if neither is
greater/lesser, but I don't know if that's standard.

Post by Ulrich Eckhardt
I guess that you will find more such problems if you try to sort sequences
containing NAN.

well... not quite, that's more predictable, because a sorting algorithm
usually relies consistently on "less" and since all "less" return false,
NANs end up to the left (I'm speaking from a practical point of view -- as a
rule I totally agree with you).
Here you have an extra source of randomness: based on the result of an
(unknown) operator, you choose one argument or the other.

[peter koch]

Post by Mycroft Holmes

Post by Ulrich Eckhardt

Post by Mycroft Holmes
does the standard say anything about the behaviour of std::min/max does on
(say, double) NAN?

I don't know the standard, but looking at the documentation for the STL, it
mentions that '<' for max/min must provide a partial ordering, which
floating point numbers that are NAN simply break.

MSDN mentions that max/min return the first element if neither is
greater/lesser, but I don't know if that's standard.

Post by Ulrich Eckhardt
I guess that you will find more such problems if you try to sort sequences
containing NAN.

well... not quite, that's more predictable, because a sorting algorithm
usually relies consistently on "less" and since all "less" return false,
NANs end up to the left (I'm speaking from a practical point of view -- as a
rule I totally agree with you).
Here you have an extra source of randomness: based on the result of an
(unknown) operator, you choose one argument or the other.

Sorry, but this is simply not correct. Calling std::sort with a
collection of doubles of which at least one is NaN causes undefined
behaviour and will in practice often have an unfortunate result such
as an infinite loop. If you want to have NaNs in your doubles, you
should provide your own comparison operator that makes the comparison
well-defined.

/Peter

[Mycroft Holmes]

Post by peter koch
Calling std::sort with a
collection of doubles of which at least one is NaN causes undefined
behaviour
will in practice often have an unfortunate result such
as an infinite loop.

can you show an example?
I think #1 is correct, but #2 in practice will not occur for subtle
algorithmical reasons.

[Igor Tandetnik]

Post by Mycroft Holmes
does the standard say anything about the behaviour of std::min/max
does on (say, double) NAN?

Yes. It says the behavior is undefined.

25.3.7 Minimum and maximum [lib.alg.min.max]
template<class T> const T& min(const T& a, const T& b);
template<class T, class Compare>
const T& min(const T& a, const T& b, Compare comp);
1 Requires: Type T is LessThanComparable (20.1.2) and CopyConstructible
(20.1.3).
2 Returns: The smaller value.
3 Notes: Returns the first argument when the arguments are equivalent.


20.1.2 Less than comparison
Table 29—LessThanComparable requirements
expression | return type | requirement
a < b | convertible to bool | < is a strict weak ordering relation
(25.3)


25.3/4 The term strict refers to the requirement of an irreflexive
relation (!comp(x, x) for all x), and the term weak to requirements that
are not as strong as those for a total ordering, but stronger than those
for a partial ordering. 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:
— comp(a, b) && comp(b, c) implies comp(a, c)
— equiv(a, b) && equiv(b, c) implies equiv(a, c)


The usual less-than relation on dobules is not a strict weak ordering in
the presence of NANs. Specifically, NAN is equivalent to any other
number ( !(NAN < x) && !(x < NAN) holds for any x), but the resulting
equiv relation is not transitive ( equiv(1.0, NAN) && equiv(NAN, 2.0)
but not equiv(1.0, 2.0) ).

[Mycroft Holmes]

Post by Igor Tandetnik
Yes. It says the behavior is undefined.

...

Post by Igor Tandetnik
3 Notes: Returns the first argument when the arguments are equivalent.

Thanks for pointing out the reference to the standard!
I think this is the clause that answers my questions: max/min see only 2
arguments at a time, so the requirement of the associated equivalence being
transitive is less stringent..