size of limb
Décio Luiz Gazzoni Filho
decio at decpp.net
Sun Aug 7 20:09:56 CEST 2005
On Aug 7, 2005, at 5:10 AM, Gunnar wrote:
> Hi.
> I have a question about the size of the limb.
> For example, if you use 32 bit limbs, do you then let the number
> stored in the
> limb be 32 bit large, or only about 16?
>
> The thing is that when multiplying these two numbers, you get eithe
> a 64 bit
> result or a 32 bit result.
> Now you have to decide which is most efficient:
> 1) handling overflow of the 64 bit number (it doesn't fit in a 32
> bit number)
> or
> 2) using only 16 bits and then using twice as many limbs.
>
> I'm interested to know how do you do this in GMP, and why did you
> decide on
> doing it that way.
>
I don't speak for the GMP guys, but I have done a little bit of
multiprecision arithmetic implementation myself, and the answer to
this question is easy.
When you look at instruction timings for multiplication and addition/
addition with carry, and the fact that a 2n-digit multiplication must
be synthesized from 4 n-digit multiplications (sure, there's
Karatsuba, but forget about it for a moment), then any overhead of
handling carries is much smaller than reducing the size of
multiplication. The P4 Prescott core is the odd man here because it
can multiply about as fast as it can do an addition with carry, so
I'm not sure this is the best solution for that core.
I speak mainly for scalar x86 here. For certain architectures which
don't produce the high part of a multiplication, or which don't
provide instruction to deal with carries (SSE2 comes to mind), the
picture may be different.
There's also another possibility which you haven't considered, a
redundant representation: there limbs are 32-epsilon bits long. There
was a paper by someone at Intel who suggested 29-bit-long limbs for
224-bit multiplication, so instead of 7 words to represent a 224-bit
integer, you used 8. The advantage being that you can do the complete
addition pyramid (after multiplications) without the need for
carries. On the other hand, converting to/from this representation is
fairly expensive.
> I'm sure this might differ between different kind of hardware/OS.
> Are there
> also any significant pros/cons regarding this problem when
> comparing "32bit
> machines" to "64 bit machins"?
>
No inherent difference from the 32-bit situation. Again, this is
architecture dependant much more than word size dependant.
Décio
-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 186 bytes
Desc: This is a digitally signed message part
Url : http://gmplib.org/list-archives/gmp-discuss/attachments/20050807/67ee50e1/PGP.bin
More information about the gmp-discuss
mailing list