Sorting floating-point values, and NaN
tn
no at email.com
Tue Nov 12 11:26:11 PST 2013
On Tuesday, 12 November 2013 at 17:59:37 UTC, Vladimir Panteleev
wrote:
> 1) As above, introduce a "less" function which guarantees
> transitivity for basic types, and use it in examples throughout.
>
> 2) Improve documentation and visibility of this problem. For
> example, add this to the documentation of sort:
>
> "The predicate must be transitive (`a<b && b<c` implies `a<c`)
> in order for `sort` to behave properly - otherwise, the program
> may fail on certain inputs (but not others) when not compiled
> in release mode. Note that `a<b` is not transitive for floating
> points, because the expression will always be `false` when
> either `a` or `b` is `NaN`."
But 'a<b' is transitive for floating points. The transitivity
condition (`a<b && b<c` implies `a<c`) says nothing about the
cases where a and b (or b and c) are incomparable. Transitivity
is not the problem
> Sort et al don't know how to check "a>=b"... and they can't use
> "a<b" either, because !(a<b) && !(b<a) implies a==b.
This is the problem, that is, the fact that with '<' you can't
tell the difference between equal values and incomparable values
(one or both are NaNs). On the other hand, with '<=' you can. See:
(a<b) && !(b<a) --> a<b
!(a<b) && (b<a) --> b<a
(a<b) && (b<a) --> (not possible)
!(a<b) && !(b<a) --> a==b OR incomparable
but
(a<=b) && !(b<=a) --> a<b
!(a<=b) && (b<=a) --> b<a
(a<=b) && (b<=a) --> a==b
!(a<=b) && !(b<=a) --> incomparable
Thus, the correct solution would be to modify the functions to
take "lessOrEqual" as a template parameter instead of "less".
If "less" is kept, then we need another template argument to
separate equality and incomparability (something like
"equals(a,b)", or "incomparable(a,b)").
More information about the Digitalmars-d
mailing list