Home  Forums  Reviews  Guides  Newsgroups  Register  Search 
Thread Tools 
nbigaouette
Guest
Posts: n/a

I need to sort a list of objects based on their position into a Zoder
[1]. Everywhere I look, zorder is used by interleaving bit representation of integers]. In my case, the objects have a double precision[2] position in three dimension. Somebody told me it would not work with double precision because the mantissa has a different meaning then the exponent. But I was not convinced and tried anyway. Actually, since the exponent is stored in higher significant bits then the mantissa, I think I could interleave the bits from the exponents, and then interleave the mantissa. So I implemented that. Hell, I even did it manually (with 32 bits floats, not 64 bits doubles). But I cannot make it work reliably. I'd like to get some comments on that... My procedure was as follow. Place 16 particles on a 4x4 grid. The positions in x and y dimensions are 1, 2, 3 and 4 bohrs[3] but expressed in meters. The initial ordering (as found in memory) is: 13 14 15 16 9 10 11 12 5 6 7 8 1 2 3 4 The 16 [x,y] positions are, in meters: [5.29177240552557e11 , 5.29177240552557e11] [1.05835448110511e10 , 5.29177240552557e11] [1.58753172165767e10 , 5.29177240552557e11] [2.11670896221023e10 , 5.29177240552557e11] [5.29177240552557e11 , 1.05835448110511e10] [1.05835448110511e10 , 1.05835448110511e10] [1.58753172165767e10 , 1.05835448110511e10] [2.11670896221023e10 , 1.05835448110511e10] [5.29177240552557e11 , 1.58753172165767e10] [1.05835448110511e10 , 1.58753172165767e10] [1.58753172165767e10 , 1.58753172165767e10] [2.11670896221023e10 , 1.58753172165767e10] [5.29177240552557e11 , 2.11670896221023e10] [1.05835448110511e10 , 2.11670896221023e10] [1.58753172165767e10 , 2.11670896221023e10] [2.11670896221023e10 , 2.11670896221023e10] As you might "see", the x dimension is incremented first, then y. I then converted these decimals to binary representation[4]: [00101110011010001011110000010000 , 00101110011010001011110000010000] [00101110111010001011110000010000 , 00101110011010001011110000010000] [00101111001011101000110100001100 , 00101110011010001011110000010000] [00101111011010001011110000010000 , 00101110011010001011110000010000] [00101110011010001011110000010000 , 00101110111010001011110000010000] [00101110111010001011110000010000 , 00101110111010001011110000010000] [00101111001011101000110100001100 , 00101110111010001011110000010000] [00101111011010001011110000010000 , 00101110111010001011110000010000] [00101110011010001011110000010000 , 00101111001011101000110100001100] [00101110111010001011110000010000 , 00101111001011101000110100001100] [00101111001011101000110100001100 , 00101111001011101000110100001100] [00101111011010001011110000010000 , 00101111001011101000110100001100] [00101110011010001011110000010000 , 00101111011010001011110000010000] [00101110111010001011110000010000 , 00101111011010001011110000010000] [00101111001011101000110100001100 , 00101111011010001011110000010000] [00101111011010001011110000010000 , 00101111011010001011110000010000] Then, I manually interleaved the x and y bits. For example, for the first position [1,1] bohr, I first put the two binary numbers one after the other. Secondly, I add a space between each digit, and third shift the lower one by adding another space at the front of it. The bit interleaving just then appears with the bits aligned: 1) 00101110011010001011110000010000 00101110011010001011110000010000 2) 0 0 1 0 1 1 1 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0 3) 0 0 1 0 1 1 1 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0 4) 00001100111111000011110011000000110011111111000000 00001100000000 Doing this manual procedure for all the combinations, I get the following: 00001100111111000011110011000000110011111111000000 00001100000000 r1 00001100111111001011110011000000110011111111000000 00001100000000 r2 00001100111111100001110011101000110001011111001000 00000110100000 r3 00001100111111100011110011000000110011111111000000 00001100000000 r4 00001100111111000111110011000000110011111111000000 00001100000000 r5 00001100111111001111110011000000110011111111000000 00001100000000 r6 00001100111111100101110011101010110001011111001000 00000110100000 r7 00001100111111100111110011000000110011111111000000 00001100000000 r8 00001100111111010010110011010100110010101111000100 00001001010000 r9 00001100111111011010110011010100110010101111000100 00001001010000 r10 00001100111111110000110011111100110000001111001100 00000011110000 r11 00001100111111110010110011010100110010101111000100 00001001010000 r12 00001100111111010011110011000000110011111111000000 00001100000000 r13 00001100111111011011110011000000110011111111000000 00001100000000 r14 00001100111111110001110011101000110001011111001000 00000110100000 r15 00001100111111110011110011000000110011111111000000 00001100000000 r16 Note that I added a name at the end to keep track of which line represent which positions. I saved that to a file, cat'ed it, and piped to "sort": $ cat to_sort.txt  sort 00001100111111000011110011000000110011111111000000 00001100000000 r1 00001100111111000111110011000000110011111111000000 00001100000000 r5 00001100111111001011110011000000110011111111000000 00001100000000 r2 00001100111111001111110011000000110011111111000000 00001100000000 r6 00001100111111010010110011010100110010101111000100 00001001010000 r9 00001100111111010011110011000000110011111111000000 00001100000000 r13 00001100111111011010110011010100110010101111000100 00001001010000 r10 00001100111111011011110011000000110011111111000000 00001100000000 r14 00001100111111100001110011101000110001011111001000 00000110100000 r3 00001100111111100011110011000000110011111111000000 00001100000000 r4 00001100111111100101110011101010110001011111001000 00000110100000 r7 00001100111111100111110011000000110011111111000000 00001100000000 r8 00001100111111110000110011111100110000001111001100 00000011110000 r11 00001100111111110001110011101000110001011111001000 00000110100000 r15 00001100111111110010110011010100110010101111000100 00001001010000 r12 00001100111111110011110011000000110011111111000000 00001100000000 r16 I now have an (almost) Zorder list. Here is a what it produces: 13 14 15 16  \  \  \   \  \  \  9 10  11 12 \  \ \  \ 5 6  7  8  \   \  \  \ \ 1 2 3  4 As you see, the 7 and 4 are inverted from what it should give (an "N" ordering, instead of "Z", but that is equivalent and irrelevant). Now if I automate all this, I get similar weird results. It is even worse when the system is big. As examples, I have ploted the ordering for a small grid (the previous example)[5], a bigger grid[6] and a big disk [7] Now I cannot belive that Zordering does not work with double precision data since I almost got it. But then, I cannot correctly get what I want... Did anybody worked with that before? Does anyone can comment on the procedure? If you spot a mistake? I absolutely need to make this working... Thanx a lot. [1] http://en.wikipedia.org/wiki/Zorder_(curve) [2] http://en.wikipedia.org/wiki/Double_precision [3] http://en.wikipedia.org/wiki/Bohr_radius [4] http://www.binaryconvert.com/convert_float.html [5] http://nbigaouette.inrsemt.homelinu...grid_small.png [6] http://nbigaouette.inrsemt.homelinu...r_grid_big.png [7] http://nbigaouette.inrsemt.homelinu...order_disk.png 




nbigaouette 


 
Gene 


 
Gene
Guest
Posts: n/a

On Nov 5, 8:47*pm, Gene <(EMail Removed)> wrote:
> On Nov 5, 6:50*pm, nbigaouette <(EMail Removed)> wrote: > > > I need to sort a list of objects based on their position into a Zoder > > [1]. Everywhere I look, zorder is used by interleaving bit > > representation of integers]. In my case, the objects have a double > > precision[2] position in three dimension. > > > Somebody told me it would not work with double precision because the > > mantissa has a different meaning then the exponent. But I was not > > convinced and tried anyway. Actually, since the exponent is stored in > > higher significant bits then the mantissa, I think I could interleave > > the bits from the exponents, and then interleave the mantissa. So I > > implemented that. Hell, I even did it manually (with 32 bits floats, > > not 64 bits doubles). > > > But I cannot make it work reliably. I'd like to get some comments on > > that... > > > My procedure was as follow. Place 16 particles on a 4x4 grid. The > > positions in x and y dimensions are 1, 2, 3 and 4 bohrs[3] but > > expressed in meters. The initial ordering (as found in memory) is: > > 13 * * *14 * * *15 * * *16 > > > 9 * * * 10 * * *11 * * *12 > > > 5 * * * 6 * * * 7 * * * 8 > > > 1 * * * 2 * * * 3 * * * 4 > > > The 16 [x,y] positions are, in meters: > > [5.29177240552557e11 , 5.29177240552557e11] > > [1.05835448110511e10 , 5.29177240552557e11] > > [1.58753172165767e10 , 5.29177240552557e11] > > [2.11670896221023e10 , 5.29177240552557e11] > > [5.29177240552557e11 , 1.05835448110511e10] > > [1.05835448110511e10 , 1.05835448110511e10] > > [1.58753172165767e10 , 1.05835448110511e10] > > [2.11670896221023e10 , 1.05835448110511e10] > > [5.29177240552557e11 , 1.58753172165767e10] > > [1.05835448110511e10 , 1.58753172165767e10] > > [1.58753172165767e10 , 1.58753172165767e10] > > [2.11670896221023e10 , 1.58753172165767e10] > > [5.29177240552557e11 , 2.11670896221023e10] > > [1.05835448110511e10 , 2.11670896221023e10] > > [1.58753172165767e10 , 2.11670896221023e10] > > [2.11670896221023e10 , 2.11670896221023e10] > > As you might "see", the x dimension is incremented first, then y. > > > I then converted these decimals to binary representation[4]: > > [00101110011010001011110000010000 , 00101110011010001011110000010000] > > [00101110111010001011110000010000 , 00101110011010001011110000010000] > > [00101111001011101000110100001100 , 00101110011010001011110000010000] > > [00101111011010001011110000010000 , 00101110011010001011110000010000] > > [00101110011010001011110000010000 , 00101110111010001011110000010000] > > [00101110111010001011110000010000 , 00101110111010001011110000010000] > > [00101111001011101000110100001100 , 00101110111010001011110000010000] > > [00101111011010001011110000010000 , 00101110111010001011110000010000] > > [00101110011010001011110000010000 , 00101111001011101000110100001100] > > [00101110111010001011110000010000 , 00101111001011101000110100001100] > > [00101111001011101000110100001100 , 00101111001011101000110100001100] > > [00101111011010001011110000010000 , 00101111001011101000110100001100] > > [00101110011010001011110000010000 , 00101111011010001011110000010000] > > [00101110111010001011110000010000 , 00101111011010001011110000010000] > > [00101111001011101000110100001100 , 00101111011010001011110000010000] > > [00101111011010001011110000010000 , 00101111011010001011110000010000] > > > Then, I manually interleaved the x and y bits. For example, for the > > first position [1,1] bohr, I first put the two binary numbers one > > after the other. Secondly, I add a space between each digit, and third > > shift the lower one by adding another space at the front of it. The > > bit interleaving just then appears with the bits aligned: > > 1) > > 00101110011010001011110000010000 > > 00101110011010001011110000010000 > > 2) > > 0 0 1 0 1 1 1 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0 > > 0 0 1 0 1 1 1 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0 > > 3) > > 0 0 1 0 1 1 1 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0 > > *0 0 1 0 1 1 1 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0 > > 4) > > 00001100111111000011110011000000110011111111000000 00001100000000 > > > Doing this manual procedure for all the combinations, I get the > > following: > > 00001100111111000011110011000000110011111111000000 00001100000000 * *r1 > > 00001100111111001011110011000000110011111111000000 00001100000000 * *r2 > > 00001100111111100001110011101000110001011111001000 00000110100000 * *r3 > > 00001100111111100011110011000000110011111111000000 00001100000000 * *r4 > > 00001100111111000111110011000000110011111111000000 00001100000000 * *r5 > > 00001100111111001111110011000000110011111111000000 00001100000000 * *r6 > > 00001100111111100101110011101010110001011111001000 00000110100000 * *r7 > > 00001100111111100111110011000000110011111111000000 00001100000000 * *r8 > > 00001100111111010010110011010100110010101111000100 00001001010000 * *r9 > > 00001100111111011010110011010100110010101111000100 00001001010000 > > r10 > > 00001100111111110000110011111100110000001111001100 00000011110000 > > r11 > > 00001100111111110010110011010100110010101111000100 00001001010000 > > r12 > > 00001100111111010011110011000000110011111111000000 00001100000000 > > r13 > > 00001100111111011011110011000000110011111111000000 00001100000000 > > r14 > > 00001100111111110001110011101000110001011111001000 00000110100000 > > r15 > > 00001100111111110011110011000000110011111111000000 00001100000000 > > r16 > > > Note that I added a name at the end to keep track of which line > > represent which positions. I saved that to a file, cat'ed it, and > > piped to "sort": > > $ cat to_sort.txt  sort > > 00001100111111000011110011000000110011111111000000 00001100000000 * *r1 > > 00001100111111000111110011000000110011111111000000 00001100000000 * *r5 > > 00001100111111001011110011000000110011111111000000 00001100000000 * *r2 > > 00001100111111001111110011000000110011111111000000 00001100000000 * *r6 > > 00001100111111010010110011010100110010101111000100 00001001010000 * *r9 > > 00001100111111010011110011000000110011111111000000 00001100000000 > > r13 > > 00001100111111011010110011010100110010101111000100 00001001010000 > > r10 > > 00001100111111011011110011000000110011111111000000 00001100000000 > > r14 > > 00001100111111100001110011101000110001011111001000 00000110100000 * *r3 > > 00001100111111100011110011000000110011111111000000 00001100000000 * *r4 > > 00001100111111100101110011101010110001011111001000 00000110100000 * *r7 > > 00001100111111100111110011000000110011111111000000 00001100000000 * *r8 > > 00001100111111110000110011111100110000001111001100 00000011110000 > > r11 > > 00001100111111110001110011101000110001011111001000 00000110100000 > > r15 > > 00001100111111110010110011010100110010101111000100 00001001010000 > > r12 > > 00001100111111110011110011000000110011111111000000 00001100000000 > > r16 > > > I now have an (almost) Zorder list. Here is a what it produces: > > 13 * * *14 * * *15 * * *16 > >  *\ * * \ * *  *\ * * > >  * *\ * *\ * * * *\ * > > 9 * * * 10 * * 11 * * *12 > > * *\ * * * * * * *\ > > * * *\ * * * * * * *\ > > 5 * * * 6 *  * 7  8 > >  *\ * * *  * * *\ > >  * *\ * * *\ * * * \ > > 1 * * * 2 * * * 3  4 > > > As you see, the 7 and 4 are inverted from what it should give (an "N" > > ordering, instead of "Z", but that is equivalent and irrelevant). Now > > if I automate all this, I get similar weird results. It is even worse > > when the system is big. As examples, I have ploted the ordering for a > > small grid (the previous example)[5], a bigger grid[6] and a big disk > > [7] > > > Now I cannot belive that Zordering does not work with double > > precision data since I almost got it. But then, I cannot correctly get > > what I want... Did anybody worked with that before? Does anyone can > > comment on the procedure? If you spot a mistake? > > > I absolutely need to make this working... > > > Thanx a lot. > > > [1]http://en.wikipedia.org/wiki/Zorder_(curve) > > [2]http://en.wikipedia.org/wiki/Double_precision > > [3]http://en.wikipedia.org/wiki/Bohr_radius > > [4]http://www.binaryconvert.com/convert_float.html > > [5]http://nbigaouette.inrsemt.homelinux.net/perso/zorder/Zorder_grid_sm... > > [6]http://nbigaouette.inrsemt.homelinux.net/perso/zorder/Zorder_grid_bi... > > [7]http://nbigaouette.inrsemt.homelinux.net/perso/zorder/Zorder_disk.png > > The people who told you that it's nonsense to mix bits of floating > point numbers were correct. *The bitinterleave algorithm exploits the > fact that bit i has a weight of 2^i. *This is only true of non > negative integers. > > In a floating point number (ignoring signs for the moment), bit i of > the mantissa has a weight of 2^(i + E) where E is the value of the > exponent. > > To get correct results, you'd need to build Morton codes by decoding > the floating point values into integers according to the above and > then bitinterleaving those integers. > > Here's the problem. *The IEEE double precision floating point format > can express a dynamic range of something like 2^(2048 + 52) = 2^2100. > (This is approximate. I'm not an IEEE format expert.) This means that > a precise but naive Mortonorder coordinate (if you don't know > anything about the range of your data) representation would need up to > roughly 2,100 bits. *Of course many of these bits will be zero, so you > could reduce the space with a fancy data structure accounting for > sparseness, but then the comparison and sorting algorithms are more > complicated. > > If you know the dynamic range of your data is small compared to the > full IEEE representation space, you should be able to do fine if you > convert your a double coords (X, Y) into e.g. 64 bit integer coords > (Xi, Yi) with something like > > Xi = floor( (X  Xmin) / (Xmax  Xmin) ) > Yi = floor( (Y  Ymin) / (Ymax  Ymin) ) > > and now build a 128bit Morton code out of Xi and Yi. > > The 64 bits integers would allow for dynamic range e.g. Xmax/Xmin > and Ymax/yMin to be roughly 2^(63  51) = 2^12 = 4096 before you'd > run into problems with multiple floating point values mapping to a > single integer. *(Check this. I'm making rough approximations again.) > > Of course if you aren't concerned with exact precision in the morton > order, you could use smaller integers and accept the fact that > coordinates close together on either axis might sort incorrectly. Sorry I typed too fast. "2^(i + E)" above is qualitative: the exct magnitude of a bit in the mantissa depends on bit numbering and where the implicit binary point lies. I'll let others work out the precise expression. Also, the naively stored Morton coordinate might have 4200 bits, not 2100. Gene 




Gene 


 
Thread Tools  


Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
question row filter (more of sql query question)  =?Utf8?B?YW5kcmV3MDA3?=  ASP .Net  2  10062005 01:07 PM 
Quick Question  Newby Question  =?Utf8?B?UnlhbiBTbWl0aA==?=  ASP .Net  4  02162005 11:59 AM 
Question on Transcender Question :)  eddiec  MCSE  6  05202004 06:59 AM 
Question re: features of the 831 router (also a 924 question)  Wayne  Cisco  0  03022004 07:57 PM 
Syntax Question  Novice Question  sean  ASP .Net  1  10202003 12:18 PM 
Powered by vBulletin®. Copyright ©2000  2014, vBulletin Solutions, Inc..
SEO by vBSEO ©2010, Crawlability, Inc. 