NTT multiplication.

[Aleksey Bader]

Hi GMP developers!

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ärnqvist and Niels Möller).

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 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.*? Is it still could be profitable in comparison with the
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önhage-Strassen on "astonomically large numbers" :-) )?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://gmplib.org/list-archives/gmp-devel/attachments/20090513/cb0f6cbc/attachment.html>