Z-order

[KBriggs]

I wonder if anyone is familiar with z-order, described here:

Z-order (curve) - Wikipedia, the free encyclopedia

Now, this algorithm works like a charm for integer values, but for doubles, simple bit-interleaving fails. Can someone explain why? Does anybody know if this has been done with double values?

Assuming that it can't be done for floating points directly, is there a way to map between integers and floating points such that the bit interleaving will work?

My problem is the range - I am sorting things from 0 to several thousand, with every order of magnitude in between, so any simple mapping that I can see would require an extremely fine grid, which is really not desireable.

[Salem]

Would taking the fixed point equivalent of the floating point number work?

Fixed point numbers are essentially integers, so that ought to work.

The only question is what is the numeric range and precision of the floats you want to process?

[KBriggs]

The range goes from 0 to inifnity in theory, but practically it shouldn't get larger than say 10,000. The precision has to be to at least 14 decimal places, so double precision.

I have never heard of fixed point numbers, could you explain a little bit what they are?

however, I can't guarantee that 10,000 is the upper bound, so I am not sure if that would work since a scaled integer cannot represent all what... 300+ orders of magnitude?

EDIT: read wikipedia on fixed point numbers, and I see the same problem. Integers cannot represent the whole range of doubles, so even if this would work in 99.999% of my cases, that 0.001% will still make all my results garbage.

[MK27]

I have never heard of fixed point numbers, could you explain a little bit what they are?

WHAT???

Money is an example of fixed precision -- it only has two decimal places, never more. So you could use a 14 decimal place fixed precision number, stored as a long int, and divide by 10^14 to get your double when necessary.

[KBriggs]

LOL, ok I can understand what the words mean, what i meant was that I have never heard of a specific computer-science related use for them that differs from floating points.

What if my number is larger than a long int? It is unlikely, but it can happen.

I have tried the mapping from doubles to ints and it works, but because of those rare cases, I can't use it. What I would really like is an explanation of why the bit-interleaving fails for doubles.

[MK27]

What if my number is larger than a long int? It is unlikely, but it can happen.

I have tried the mapping from doubles to ints and it works, but because of those rare cases, I can't use it.

Any number that fits into a double will fit into a long int. They are the same size. Can it be unsigned?

[bithub]

Any number that fits into a double will fit into a long int. They are the same size.

They are not the same size. A double is usually 64 bits, and a long int is usually 32 bits. The can vary depending on the platform, but you definitely cannot say they are always (or often) the same size.

[KBriggs]

This format gives a range of approximately 1.7E–308 to 1.7E+308 for type double.

Long ints can't get that big... And no, it can't be unsigned.

[MK27]

They are not the same size. A double is usually 64 bits, and a long int is usually 32 bits. The can vary depending on the platform, but you definitely cannot say they are always (or often) the same size.

Ah. Well, on my 64-bit system:

printf ("%d %d\n",sizeof(long int),sizeof(double));

They are both 64 bits, so I guess that could be "often" but not "often enough".

[KBriggs]

Even if it did work that way on my system, this is really an optimization, and the integer mapping didn't give me much of a boost because of how fine the 'grid' had to be.

Can anyone explain why the bit-interleaving fails for floating points? Perhaps I can work out an alternate way to interleave them that gives the desired result if I know why it fails in the first place.

[KBriggs]

Hm, could the problem lie in the sign bit? How does the binary representation of integers code for sign? Is it different from the way doubles do?

[bithub]

How does the binary representation of integers code for sign? Is it different from the way doubles do?

Yes it is different. Integers use 2s compliment to represent negative numbers.

[KBriggs]

So the first bit of an integer says nothing about the sign?

[brewbuck]

Even if it did work that way on my system, this is really an optimization, and the integer mapping didn't give me much of a boost because of how fine the 'grid' had to be.

Can anyone explain why the bit-interleaving fails for floating points? Perhaps I can work out an alternate way to interleave them that gives the desired result if I know why it fails in the first place.

Z-ordering works because the Nth bit in one quantity represents the same magnitude as the Nth bit in another quantity. But for floating point, this is not the case, since floats are represented as a product of mantissa and exponent -- therefore the Nth bit in value A might represent a quantity that is many, many orders of magnitude different from the Nth bit of value B.

The floats have to be normalized to all have the same exponent before bit-interleaving. This is inappropriate, because the exponential representation means you might need many hundreds of bits to do so, and most of these bits will be zero because of logarithmic data density. PLEASE, read up some more about floating point

EDIT: Think about what a logarithm does. If some floating point value is A*2^N then the logarithm of this is log(A) + Log(2^N) = log(A)+N*log(2). Now the values differ only by a linear shift (a multiple of N, where N is the exponent), and presuming that the range of exponents is reasonably small, can be ignored. In other words, take the logarithms of the values, cast to integer, and use this in the z-order. Of course, you lose information in the casting.

EDIT EDIT: The amount of error contained in the z-order will be lessened if you represent the numbers in a higher base (instead of binary). Imagine interleaving the DECIMAL digits of the values, for instance. Because the system base is 10, the effect of the ranging exponents will be lessened. Higher and higher bases work better, until the maximum exponent different represents a shift of less than a single digit, at which point the approximation is optimal... yadda yadda

[KBriggs]

Thanks very much, that is exactly the information I was looking for