12

If have an 8-byte section of data and write a double-precision floating-point value to it, under what conditions will comparison by numerical comparison and lexicographic sorting of the bytes agree?

Current theory: positive, big-endian

I believe that if the number is positive, and the representation is big-endian, then numerical ordering of the floating-point values will match the lexicographic ordering of the bytes.

The idea is that it would first sort on the exponent, then on the mantissa. Even the "denormalized" IEEE representation shouldn't cause any problems.

Is this true?

(I'm using Node's Buffer::writeDoubleBE, but that shouldn't matter.)

Follow-up

I think a simple modification can extend this to negative numbers: XOR all positive numbers with 0x8000... and negative numbers with 0xffff.... This should flip the sign bit on both (so negative numbers go first), and then reverse the ordering on negative numbers. Does anyone see a problem with this?

3
  • Though not C++, java Math has nextUp and similar functions for extensive unit tests.
    – Joop Eggen
    Apr 8, 2017 at 19:40
  • @JoopEggen I was hoping for a universal "no" or "provably yes". When it comes to bit-level stuff, running tests on a couple of consumer machines I have to hand doesn't give me enough confidence. I was hoping someone with slightly lower-level experience than me could say "yes this will work on all architectures, given XYZ".
    – cloudfeet
    Apr 8, 2017 at 22:34
  • 1
    Note: with this approach, -NaN values are sorted lower than -Inf and +NaN greater than +Inf. Depending on the use-case, this may or may not make sense (it breaks the assumption that ±Inf are the boundaries for the range of possible values —on the other hand, where else would it make sense to sort NaN values to, except outside the range of "numbers"?)
    – saxbophone
    Jul 25, 2022 at 18:56

2 Answers 2

13

Your approach:

I think a simple modification can extend this to negative numbers: XOR all positive numbers with 0x8000... and negative numbers with 0xffff.... This should flip the sign bit on both (so negative numbers go first), and then reverse the ordering on negative numbers. Does anyone see a problem with this?

is definitely the answer. Moreover, it was used, for example, in dBase and clones to organize sorting on a float column, and I guess it's followed by newer DB generations.

Also, it is identical to the "total order" according to IEEE-754 for binary representations. (But not for decimal ones, the latter is much more complex.)

UPDATE: as suggested by @Sneftel: you could find replacing -0 with +0 as useful before converting to bit string.

3
  • The one actually meaningful issue: This will cause -0 to compare less than +0. The probably-not-important issue: NaNs will not be correctly "unordered".
    – Sneftel
    Apr 9, 2017 at 20:20
  • @Sneftel according to public drafts of IEEE754-2008, all this is according to totalOrder predicate: -0 is less than +0; order for NaNs are exactly just with this comparison. Seems that totalOrder was intentionally defined to be trivially implemented with this method. If you care only for -0/+0, this case can be reflected separately (e.g. replace -0 with +0 before converting).
    – Netch
    Apr 10, 2017 at 4:10
  • Yes, I was referring to the OP's desire for numerical comparison.
    – Sneftel
    Apr 10, 2017 at 6:52
2

If you want to let Radix sorting stay a stable sorting algorithm, you have to swap all subsections of equal elemts in the negative section once more, because when you swaped the negative numbers, the original stable sorting were in stable order.

Assoc. prof. Arne Maus, Univ of Oslo

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.