Morton Numbers Questions

[James M.]

I am using MPIR to calculate Morton numbers or Z-curve indexes for high dimensional data for gamma-ray coincidence analysis. While not truly meant for this, they work fantastically, so thank you very much for that.
Anyways I was wondering a few things:

First of all, does anyone have any suggestions for a a good way to write an integer dilation function? As a quick, get it working, implementation I pretty much preallocate an mpz_class to the appropriate size and then set each bit.
Obviously this is... not optimal. So I have been looking at taking the coordinate value for each dimension, placing it into a preallocated mpz_class and adding zeros between the bits. If I do this for each dimension then all I have to do is a little bitshifting and addition to get the Morton number. If anyone has suggestions or advice it would be welcome.

Second of all, all I use is the C++ integers portion of MPIR, mostly the bit manipulation in fact, how difficult is it to trim the source down to that? I don't really use all the super fancy bit of the integers either but I realize that those would be harder trim out.

Anyways, thanks for reading my possibly (probably) inane questions.
--
James M

[Bill Hart]

The big problem with setting bits and shifting is that it is a
quadratic algorithm. It will be much slower than setting the
individual bits.

The best idea would be to set the top bit first, then set the other bits.

The fastest method would use mpn's instead of mpz's, but this requires
considerably more work and may not be appropriate.

As for cutting out portions of MPIR, this would be a massive job I am
afraid. I wouldn't recommend spending valuable time doing that.

Bill.

> --
> You received this message because you are subscribed to the Google Groups
> "mpir-devel" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/mpir-devel/-/ZoSw11GEucoJ.
> To post to this group, send email to mpir-...@googlegroups.com.
> To unsubscribe from this group, send email to
> mpir-devel+...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/mpir-devel?hl=en.
>
>

[James M.]

Thanks for the quick reply.
Why the setting of the top bit first?
I will certainly look into the mpn functions for implementation, as I keep all handling of mpir and calculation of the morton numbers restricted to the interior of a single class, even if it is tricky to get done I only need to do it once and any additional insanity will not propagate through my code.
As for why I was mentioning the shifting was because if I have an d-dimensional point with n bits in each coordinate then the full calculation of a z-curve coordinate requires as follows:
//this part actually happens in the constructor, the mpz_t is called index
mpz_init2( index, (n*d) );
//now for the actual morton number calculation
for(int i=0; i<d; ++i)
{
    if( (coord[i] & 0x01ULL)==1 )
    {
        mpz_setbit( index, i );
    }
    for(int j=1; j<n; ++j)
    {
        if( ((coord[i]>>j)&0x01ULL)==1 )
        {
            mpz_setbit( index, (j*n+i) );
        }
    }
}

anyways this takes an average of n*d/2 mpz bitset operations plus (d-1)*n 64bit bit shifts plus d*n 64bit bitwise and plus d*n comparisons

looking here: http://graphics.stanford.edu/~seander/bithacks.html#Interleave64bitOps and here: http://www.cs.indiana.edu/~dswise/Arcee/castingDilated-comb.pdf made me think that it must be possible to do better than this, though perhaps there are details coming from the internals of MPIR that I am unaware of.

As to the chopping out parts of MPIR I only asked because when I sent the early version of my code to a few people they complained a little about having to build and install the libraries and so I thought for a bit about cutting out what I did not need and simply compiling it with my code. This was just a thought though.
--
James

[Bill Hart]

On 01/09/2012, James M. <james...@gmail.com> wrote:
> Thanks for the quick reply.
> Why the setting of the top bit first?

This is just to ensure sufficient memory is allocated.

> I will certainly look into the mpn functions for implementation, as I keep
> all handling of mpir and calculation of the morton numbers restricted to
> the interior of a single class, even if it is tricky to get done I only
> need to do it once and any additional insanity will not propagate through
> my code.

If you are after absolutely optimal performance then it may be
worthwhile. Though you'll end up doing a lot of the bit setting by
hand I think.

> As for why I was mentioning the shifting was because if I have an
> d-dimensional point with n bits in each coordinate then the full
> calculation of a z-curve coordinate requires as follows:
> //this part actually happens in the constructor, the mpz_t is called index
> mpz_init2( index, (n*d) );
> //now for the actual morton number calculation
> for(int i=0; i<d; ++i)
> {
> if( (coord[i] & 0x01ULL)==1 )
> {
> mpz_setbit( index, i );
> }
> for(int j=1; j<n; ++j)
> {
> if( ((coord[i]>>j)&0x01ULL)==1 )
> {
> mpz_setbit( index, (j*n+i) );
> }
> }
> }
>
> anyways this takes an average of n*d/2 mpz bitset operations plus (d-1)*n
> 64bit bit shifts plus d*n 64bit bitwise and plus d*n comparisons

Ah I see. I thought you meant you were doing multiple precision bitshifts.

>
> looking here:
> http://graphics.stanford.edu/~seander/bithacks.html#Interleave64bitOps and
> here: http://www.cs.indiana.edu/~dswise/Arcee/castingDilated-comb.pdf made
> me think that it must be possible to do better than this, though perhaps
> there are details coming from the internals of MPIR that I am unaware of.

Your code doesn't look too bad to me. Though with mpn's you could
combine the index calculations with the bitset indexing calculations
perhaps.

>
> As to the chopping out parts of MPIR I only asked because when I sent the
> early version of my code to a few people they complained a little about
> having to build and install the libraries and so I thought for a bit about
> cutting out what I did not need and simply compiling it with my code. This
> was just a thought though.
> --
> James

Bill.

>
> On Friday, August 31, 2012 11:20:23 PM UTC-4, Bill Hart wrote:
>>
>> The big problem with setting bits and shifting is that it is a
>> quadratic algorithm. It will be much slower than setting the
>> individual bits.
>>
>> The best idea would be to set the top bit first, then set the other bits.
>>
>>
>> The fastest method would use mpn's instead of mpz's, but this requires
>> considerably more work and may not be appropriate.
>>
>> As for cutting out portions of MPIR, this would be a massive job I am
>> afraid. I wouldn't recommend spending valuable time doing that.
>>
>> Bill.
>>

>> > mpir-...@googlegroups.com<javascript:>.

>>
>> > To unsubscribe from this group, send email to

>> > mpir-devel+...@googlegroups.com <javascript:>.

>> > For more options, visit this group at
>> > http://groups.google.com/group/mpir-devel?hl=en.
>> >
>> >
>>
>

> --
> You received this message because you are subscribed to the Google Groups
> "mpir-devel" group.
> To view this discussion on the web visit

> https://groups.google.com/d/msg/mpir-devel/-/ShaRIN_1_5oJ.