jo at durchholz.org
Fri Apr 2 08:43:36 CEST 2004
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.
More information about the gmp-discuss