NTT multiplication.

Paul Zimmermann Paul.Zimmermann at
Wed May 13 10:10:12 CEST 2009

       Dear Aleksey,

> I have a couple of questions about FFT-based multiplication algorithms in
> GMP.
> As follows from 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<>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
1000000    0.559915000

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

This code is available from <>. You'll have to
do a few changes to compile it with GMP 4.3.0 (we might publish a new version).

Paul Zimmermann

More information about the gmp-devel mailing list