NTT multiplication.

[Paul Zimmermann]

       Dear Aleksey,

> I have a couple of questions about FFT-based multiplication algorithms in
> GMP.
> 
> As follows from http://gmplib.org/projects.html one of the projects is
> devoted to implementation of FFT-based algorithm combined with Chinese
> Reminder Theorem. It's claimed that there are 2 implementations of this
> algorithm (by Tommy F=E4rnqvist and Niels M=F6ller).
> 
> Q1. Are there available source code for those implementations?
> 
> The reason I'm asking is because I did the same job when I was working on m=
> y
> master thesis 2 years ago. It'd be very curious to compare or maybe improve
> our implementations.
> Actually, I was able to find Tommy's master thesis and his code seemed to b=
> e
> up to twice as fast as the code in GMP 4.1.4.
> 
> Q2. What about 4.3.*? Is it still could be profitable in comparison with th=
> e
> current GMP multiplication? (sorry for such dump question, but I'm not
> followed gmp changes)
> 
> Thanks in advance,
> Aleksey
> 
> P.S. Reletevly recent, Martin Furer
> published<http://www.cse.psu.edu/%7Efurer/Papers/mult.pdf>new
> multiplication algorithm with very low asymptotic complexity.
> Q3. Any known (tries of) implementions (in GMP O:)? Maybe someone think
> about it (disregard to author's claim that his method outperforms
> Sch=F6nhage-Strassen on "astonomically large numbers" :-) )?

with Pierrick Gaudry and Alexander Kruppa, we have published some FFT code
(still using Schönhage-Strassen) which outperformed GMP 4.2.x by a factor 2
for some sizes, and still outperforms GMP 4.3.0 by a factor of 1.45 for some
sizes (for example for 10^6 limbs on a Core 2):

quiche% ./speed -s1000000 mpn_mul_fft # vanilla gmp-4.3.0
          mpn_mul_fft
1000000    0.559915000

quiche% ./speed -s1000000 mpn_mul_fft # gmp-4.3.0 with our FFT code
          mpn_mul_fft
1000000    0.385942000

This code is available from <http://www.loria.fr/~kruppaal/>. You'll have to
do a few changes to compile it with GMP 4.3.0 (we might publish a new version).

Paul Zimmermann