DTAshley at aol.com
DTAshley at aol.com
Fri Apr 2 14:48:58 CEST 2004
This might be a candidate for inclusion in the GMP. As everyone on this list
knows, speed is achieved by optimizing those things that happen often and
paying less attention to those that happen less often.
Given an M-bit and an N-bit integer to be interleaved, given the current
design of the GMP, I don't see a way to do it in less than about 3 * max(M,N)
On the other hand, if one included a function call to "spread" bits of an
integer with an optional spread value and optional shift, it could be expressed
SPREAD(M, 1, -1) OR SPREAD(N, 1, 1)
or something like that, which is 3 function calls regardless of integer size.
I haven't checked the GMP recently--maybe some kind of a "spread" operation
exists? In any case, if not, it seems like a good low-level bit manipulation
function to add.
BTW, by the definition above,
SPREAD(3, 1, 0) = 1010_2
SPREAD(3, 2, 0) = 100100_2
SPREAD(3, 3, 0) = 10001000_2
SPREAD(3, 3, -1) = 1000100_2
SPREAD(3, 3, 1) = 100010000_2
Best regards, Dave.
In a message dated 4/2/2004 12:43:51 AM Eastern Standard Time,
jo at durchholz.org writes:
> Hi all,
> I need to bit-interleave large integers.
> A typical example would be four integers aaa, bbb, ccc, and ddd, with an
> interleaved result of abcdabcdabcdabcd (each letter stands for a single
> Typical integer size would be about 80 bits.
> This is a mass application: there are *lots* of tuples to be interleaved.
> I have taken a look at GMP, and while it seems easy enough to extract
> the bits and set them in the result, I'm thinking about optimization
> The question being, of course: is it worth the trouble?
> I see two angles of attack:
> 1) Write C routines that do the interleaving directly on the
> representation level. Downside: constant maintenance overhead for
> keeping in sync with GMP updates. Advantage: seems to be fastest.
> 2) Construct the result integer object first, making sure that it is
> large enough to take up the result value, so there will be no
> unnecessary reallocations. Might be easy to do, too, simply by starting
> with the most significant bit.
> Comments? Advice?
> gmp-discuss mailing list
> gmp-discuss at swox.com
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the gmp-discuss