Bit interleaving

[DTAshley at aol.com]

Hi Paul,

I believe you are perhaps asking the wrong question.

Let's examine the "baggage" argument more closely.

Jo has indicated that he has an application that he can't implement 
efficiently without at the very least peeking into GMP internals or making assumptions 
about them.  He indicated his reservations about effectively extending the GMP 
and then having to support it.

IMHO, the mission of the GMP is to support the "high-frequency" interactions 
that occur when one uses large integers.  The "low-frequency" interactions can 
be handled by the clients of the GMP while still keeping both efficiency and 
good modularization.

Notice that the GMP already contains number theoretic functions such as 
Miller-Rabin.  Notice also that the GMP contains efficiency moves, such as division 
by a limb.

Why are these things in the GMP?

What is the dividing line between what goes in the GMP and what does not?

Very simply, the dividing line is whether the client of the GMP can 
efficiently do what it wants to do without that functionality.

If the client can work efficiently without the functionality, exclude it.

If the client cannot work efficiently without the functionality, include it.

Here is an example of that test applied.  Let's assume that I want to find 
the continued fraction expansion of a rational number, perhaps a rational number 
with large integer components.  Does the "continued fraction" stuff go in the 
GMP?

One might notice that a continued fraction expansion is O(log N).  There are 
a "small" number of integer operations involved (an O[log N] number of 
divisions, etc.).  Therefore, asymptotically as the integers get larger, the number 
of operations outside the GMP (divisions, zero tests, etc.) will be small 
compared with the number of operations that occur inside the GMP (limb operations). 
 Therefore, the efficiency will be good.  Therefore, there is not enough 
benefit to including continued fraction expansion inside the GMP, as the client 
can do it efficiently with the simpler interface provided.

You gave this example:

BEGIN
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.
END

Whether to include support for "elliptic curves over fields" is not the right 
question.

The right question is "What low-level primitives need to be present in the 
GMP so that the client can handle elliptic curves over fields efficiently?".

One does not need to provide support for "elliptic curves over fields".  One 
just needs to provide a type of support so that the client can do it 
efficiently.  That is the "minimal baggage" approach.

Now, back to Jo's question:

Jo gave an example of an application where the right low-level primitives in 
the GMP do not exist to implement the application efficiently.

Figure out the right low-level primitives.

Add them to the GMP.

It isn't necessary to add too much "baggage" to the GMP.  It is only 
necessary to add enough baggage to support clients efficiently.

Best regards, Dave.

In a message dated 4/2/2004 8:11:30 AM Eastern Standard Time, 
pleyland at microsoft.com writes:


> Let me guess: you want to do arithmetic in F_{2^n}.
>  
> 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.
>  
>  
> Paul
> 
> >> From: gmp-discuss-bounces at swox.com [mailto:gmp-discuss-bounces at swox.com] 
>> On Behalf Of DTAshley at aol.com
>> Sent: 02 April 2004 13:49
>> To: jo at durchholz.org; gmp-discuss at swox.com
>> Subject: Re: Bit interleaving
>> 
>> 
>> 
>> 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/840fe1af/attachment-0001.htm