Bit interleaving

[DTAshley at aol.com]

Hi Jo,

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) 
function calls.

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 
as:

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 
> bit).
> 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 
> opportunities.
> 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?
> 
> Regards,
> Jo
> _______________________________________________
> gmp-discuss mailing list
> gmp-discuss at swox.com
> https://gmplib.org/mailman/listinfo/gmp-discuss
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: /list-archives/gmp-discuss/attachments/20040402/28cec90b/attachment.htm