GMP 4.3 multiplication performance

David Harvey dmharvey at
Sun Jun 7 15:49:09 CEST 2009

On Jun 7, 2009, at 9:06 AM, Torbjorn Granlund wrote:

>   One case in which I am particularly interested is the 2n * n
>   unbalanced multiplication. This should be no more expensive than
>   twice the cost of an n * n multiplication, plus O(n) overhead that
>   should be negligible for large n.
> I think it should be slightly cheaper than twice the cost of two n * n
> multiplications.

Yes, on theoretical grounds, what I would expect to see is the ratio M 
(2n,n) / M(n,n) = 2 for small n, decreasing gradually towards 1.5 for  
very large n. (Here M(m,k) = time for m limbs * k limbs multiplication.)


More information about the gmp-devel mailing list