Sorting floating-point values, and NaN

[Vladimir Panteleev]

On Tuesday, 12 November 2013 at 20:03:37 UTC, Andrei Alexandrescu 
wrote:
>> Both of the above hinge on the relative obscurity of NaNs and 
>> the
>> problems they could cause. People who are not specifically 
>> familiar with
>> NaNs and how they interact with other floating-point values 
>> will treat
>> floating-point values as "just numbers", and expect them to 
>> compare and
>> sort in the same way as integers.
>
> I think that's their problem, not ours.

(I partially disagree here - see my reply to Walter.)

>> 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.
>
> It really implies "a and b are in the same equivalence class". 
> Building on that notion, we can figure what's wrong with NaNs 
> and how to assert against their failings.
>
> Consider we define equiv(a, b) as (a, b) => !less(a, b) && 
> !less(b, a).
>
> If at least one of the numbers is NaN, all comparisons return 
> false. That puts NaN in the same equivalence class with all 
> numbers, including numbers that are deemed in distinct 
> equivalence classes. That's where NaNs mess things up, and 
> that's what we need to assert. Consider three numbers a, b, and 
> c. Then the following must pass:
>
> assert((equiv(a, b) && equiv(b, c)) <= equiv(a, c));

OK, we're on the same page so far (although you've presented the 
problem more eloquently).

> ("<=" on Booleans is actually implication.)

(Cool!)

> That test will fail with NaNs and should be part of isSorted, 
> sort etc.

OK, but which a, b and c will be checked? Taking all adjacent 
triples will not work with two adjacent NaNs.

> We should also check such as:
>
> assert(!less(a, a));
> assert(less(a, b) <= !less(b, a));

Again, for which a/b?