Bit interleaving

[Joachim Durchholz]

Paul Leyland wrote:

> Let me guess: you want to do arithmetic in F_{2^n}.

No, not at all - I don't even know what that is :-)

I need this interleaved representation to establish a sort order on 
spatial/temporal data, for reasons too technical to detail here.

> If this is the case, an obvious solution is to extend GMP more
> generally by adding F_{2^n} tothe rings and fields Z, Z_n, R and Q
> for which GMP arithmetic is already implemented.
> 
> The obvious question is then: where do you stop. Are p-adics inside
> the fence? Algebraic number fields? Elliptic curves over fields?
> Sooner or later you end up with something that contains vast amounts
> of baggage that most people hardly ever use.

That "spread" function sounds good enough for my purposes. Whether it's 
generally useful enough to warrant inclusion in GMP is beyond my 
knowledge - I don't have much background knowledge about all the 
applications that GMP might be useful for.

Note that I can't say yet whether it's really important for me. The 
application that needs that bit-interleave stuff is still in the 
planning phase, and any predictions on bottlenecks are chancy anyway. 
Besides, the app is going to do a lot of things besides bit 
interleaving, so I can't tell whether speeding the bit interleave part 
will make it faster by 30%, 5%, or 1%.
Right now, the best I can predict is that it *may* become a bottleneck, 
and my question was motivated by the desire to know whether there's an 
optimization path in case I need it.

Regards,
Jo