size of limb

[Décio Luiz Gazzoni Filho]

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/016ca2ad/PGP.bin