Sorting floating-point values, and NaN

qznc qznc at web.de
Mon Nov 11 23:33:56 PST 2013


On Tuesday, 12 November 2013 at 04:41:56 UTC, Vladimir Panteleev 
wrote:
> double[] arr = [1, 2, 3, double.nan, 1, 2];
> assert(arr.isSorted);
> arr.sort();
>
> This code will fail with an assert error, but not the one on 
> the second line. Rather, it will fail inside std.range, when 
> sort calls assumeSorted, which checks elements in an order 
> different than sort and isSorted.
>
> Here's a case where the odd way NaN interacts with generic code 
> messes things up in an ugly way.
>
> This is concerning. It's very easy to overlook this while 
> writing an application, and it can become a hidden 
> vulnerability.
>
> We can't fix the operators... but, perhaps, we could define a 
> safe default comparison predicate (e.g. std.algorithm.less) for 
> use with sorting and related tasks? Aside from bitwise 
> comparison, is it even possible to efficiently compare 
> floating-point values in a way suitable for sorting?

You cannot sort NaNs. A comparison with NaN must always evaluate 
to false.

One could change isSorted to check for false instead of true, so 
it would accept NaN. That would probably break too much code, 
though.

   arr[n] < arr[n+1]  => !(arr[n+1] < arr[n])

Apparently, isSorted contains an antisymmetry check, which is not 
triggered, because it relies on true results.


More information about the Digitalmars-d mailing list