Float & signed int slot encoding: guarantee lexicographic ordering #2
Description
Floats can be interpreted as sign-and-magnitude integers, while keeping the same ordering. This is close to lexicographic ordering, but not quite there (every ellipsis is all zeroes):
1…11 -3
1…10 -2
1…01 -1
1…00 -0
0…00 +0
0…01 +1
The IEEE float and double formats were designed so that the numbers are “lexicographically ordered”, which – in the words of IEEE architect William Kahan means “if two floating-point numbers in the same format are ordered ( say x < y ), then they are ordered the same way when their bits are reinterpreted as Sign-Magnitude integers.” http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm
This can be made to match the usual ordering with something like the following:
- if highest bit is set (= negative), flip all bits of the float.
- if highest bit is not set (= positive), flip the sign bit
Having input with someone who deals with floats more would be useful. I mostly play with just integers.
Resources
- "Non-Extended encodings are all “Lexicographically Ordered,”"
https://www.cs.berkeley.edu/~wkahan/ieee754status/IEEE754.PDF
(non-extended as in float32 and float64, it seems)- on x86 that seems to hold after reversing the bytes
(math.Float64bits then BigEndian) - only true for positive numbers, negative floats have a problem
comparable to the zigzag encoding requirement
- on x86 that seems to hold after reversing the bytes
- "The IEEE float and double formats were designed so that the numbers
are “lexicographically ordered”, which – in the words of IEEE
architect William Kahan means “if two floating-point numbers in the
same format are ordered ( say x < y ), then they are ordered the
same way when their bits are reinterpreted as Sign-Magnitude
integers.”"
http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm
has a solution - see also Encode variable length types in lexicographic sort ordering danburkert/bytekey#1
Not directly related but interesting: