GMP 4.3 multiplication performance
David Harvey
dmharvey at cims.nyu.edu
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.)
david
More information about the gmp-devel
mailing list