NTT multiplication.
Torbjorn Granlund
tg at gmplib.org
Wed May 13 10:35:45 CEST 2009
Aleksey Bader <bader at newmail.ru> writes:
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ärnqvist and Niels Möller).
Q1. Are there available source code for those implementations?
I don't know. I think both are still work-in-progress (although the
progress might be limited for some periods). You might want to ask the
authors.
The reason I'm asking is because I did the same job when I was working on my
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 be
up to twice as fast as the code in GMP 4.1.4.
Q2. What about 4.3.*? Could it still be profitable in comparison with the
current GMP multiplication?
IIRC, his code can still beat the Schönhage-Strassen code currently in
GMP, but only for very large operands. This is due to the memory
locality tricks Tommy are using (due to Cooley and Tukey, rediscovered
by Bailey).
P.S. Relatively recently, 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önhage-Strassen on "astonomically large numbers" :-) )?
The complexity of Fürer's algorithm is only slightly better than that of
Schönhage-Strassen's algorithm. (A log(log(n)) factor is replaced by a
2^{log*(n)} factor. While a better upper bound is a nice step forward
in theoretical terms, this small improvement would probably be hard to
translate into actual performance.
--
Torbjörn
More information about the gmp-devel
mailing list