Bill Allombert on Mon, 02 May 2005 18:24:43 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: GMP performance


On Fri, Apr 29, 2005 at 04:12:12PM -0400, Igor Schein wrote:
> Hi,
> 
> GMP much slower.  Is it a tuning issue or intrinsic problem?

In fact, it is sufficient to test the squaring:

With GMP:
? #
   timer = 1 (on)
? a=2^(2^26);
time = 50 ms.
? a^2;
time = 8,990 ms.
? (a-1)^2;
time = 8,560 ms.

Without:
? #
   timer = 1 (on)
? a=2^(2^26);
time = 60 ms.
? a^2;
time = 310 ms.
? (a-1)^2;
time = 4mn, 5,740 ms.

What happen is that PARI/GP Karatsuba squaring algorithm
remove all trailing 0 words, so here it really only multiply the final
word.

GMP use the FFT but does not discard the leading 0 word, apparently.

(when using Karatsuba, you can remove all trailing 0 words (and leading
0) in all recursion chunk, so you can expect to remove a fair number of
them, not just the trailing one of the initial input. Therefore it has 
a better cost/frequency ratio.)

Cheers,
Bill.