Re: GMP performance

[Bill Allombert <allomber@math.u-bordeaux.fr>]

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.