dmharvey at cims.nyu.edu
Thu Jun 18 15:52:47 CEST 2009
On Jun 18, 2009, at 3:48 AM, Paul Zimmermann wrote:
>>> and already save more than 33% at 55 limbs. Larger timings in the
>>> range (say 100,000, 1M, 10M, 100M and 1G limbs) would be
>>> interesting too.
>> 10^4 | 4.09e+07 | 2.53e+07 | 0.619 |
>> 10^5 | 9.68e+08 | 7.99e+08 | 0.825 |
>> 10^6 | 1.90e+10 | 2.70e+10 | 1.421 |
>> That's the karatsuba asymptotics starting to dominate. At these sizes
>> surely it is better to use the FFT wraparound than to use my
> don't you also have a Toom-Cook 3-way mulmid?
(a) I don't trust the code, and
(b) the size where it starts to beat karatsuba is about the same as
where the FFT wraparound beats karatsuba, so I don't really see the
point. Unless someone can figure out how to make it much more efficient.
More information about the gmp-devel