Bit interleaving
DTAshley at aol.com
DTAshley at aol.com
Fri Apr 2 15:55:31 CEST 2004
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
More information about the gmp-discuss
mailing list