On 01/09/2012, James M. <jamesma...@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.
>>
>> On 31/08/2012, James M. <james...@gmail.com <javascript:>> wrote:
>> > 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
>> >
>> > --
>> > 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<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.
> To post to this group, send email to mpir-devel@googlegroups.com.
> To unsubscribe from this group, send email to
> mpir-devel+unsubscr...@googlegroups.com.
> 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 post to this group, send email to mpir-devel@googlegroups.com.
To unsubscribe from this group, send email to
mpir-devel+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/mpir-devel?hl=en.
