Z-order

This is a discussion on Z-order within the C Programming forums, part of the General Programming Boards category; I wonder if anyone is familiar with z-order, described here: Z-order (curve) - Wikipedia, the free encyclopedia Now, this algorithm ...

  1. #1
    Registered User
    Join Date
    Jun 2009
    Posts
    452

    Z-order

    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.
    Last edited by KBriggs; 08-04-2009 at 01:58 PM.

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,668
    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?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Jun 2009
    Posts
    452
    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.
    Last edited by KBriggs; 08-04-2009 at 02:36 PM.

  4. #4
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by KBriggs View Post
    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.
    Last edited by MK27; 08-04-2009 at 02:40 PM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  5. #5
    Registered User
    Join Date
    Jun 2009
    Posts
    452
    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.
    Last edited by KBriggs; 08-04-2009 at 02:45 PM.

  6. #6
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by KBriggs View Post
    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?
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  7. #7
    Registered User
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,246
    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.
    bit∙hub [bit-huhb] n. A source and destination for information.

  8. #8
    Registered User
    Join Date
    Jun 2009
    Posts
    452
    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.
    Last edited by KBriggs; 08-04-2009 at 03:29 PM.

  9. #9
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by bithub View Post
    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".
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  10. #10
    Registered User
    Join Date
    Jun 2009
    Posts
    452
    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.

  11. #11
    Registered User
    Join Date
    Jun 2009
    Posts
    452
    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?

  12. #12
    Registered User
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,246
    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.
    bit∙hub [bit-huhb] n. A source and destination for information.

  13. #13
    Registered User
    Join Date
    Jun 2009
    Posts
    452
    So the first bit of an integer says nothing about the sign?

  14. #14
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,249
    Quote Originally Posted by KBriggs View Post
    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
    Last edited by brewbuck; 08-04-2009 at 05:14 PM.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  15. #15
    Registered User
    Join Date
    Jun 2009
    Posts
    452
    Thanks very much, that is exactly the information I was looking for

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Laplace Expansion
    By Leojeen in forum C Programming
    Replies: 7
    Last Post: 10-28-2008, 11:26 PM
  2. Embedded SQL Order By
    By cjohnman in forum C Programming
    Replies: 12
    Last Post: 04-15-2008, 03:45 PM
  3. Header file include order
    By cunnus88 in forum C++ Programming
    Replies: 6
    Last Post: 05-17-2006, 03:22 PM
  4. How do you order your game code?
    By Queatrix in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 02-05-2006, 05:26 PM
  5. what is the significance of low order and high order bits
    By Shadow12345 in forum Windows Programming
    Replies: 1
    Last Post: 11-16-2002, 10:46 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21