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.