Sorting floating-point values, and NaN

[Andrei Alexandrescu]

On 11/12/13 1:03 PM, tn wrote:
> On Tuesday, 12 November 2013 at 20:03:37 UTC, Andrei Alexandrescu wrote:
>> 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));
>>
>> ("<=" on Booleans is actually implication.)
>
> Shouldn't the implication be to the other direction? Then it becomes
>
> assert((equiv(a, b) && equiv(b, c)) => equiv(a, c));

It is in the other direction, but the latter doesn't compile :o). Again, 
it just turns out "a <= b" has the meaning of "a implies b". It's not a 
particularly intuitive way to express it.

>> That test will fail with NaNs and should be part of isSorted, sort etc.
>
> But it requires that the input contains at least three elements. And it
> has to test a lot of possible triples (a,b,c), which I think requires at
> least O(n^2) time. And it does not fail consistently whenever the input
> contains at least one NaN (consider an input that contains only NaNs).

I agree. Ideas?

>> We should also check such as:
>>
>> assert(!less(a, a));
>> assert(less(a, b) <= !less(b, a));
>>
>> These should be checked in sort only; isSorted does not need these.
>
> The latter fails also if a==b. (Unless the direction of the implication
> is again wrong.)

Try it!


Andrei