NTT multiplication.
Torbjorn Granlund
tg at gmplib.org
Fri May 15 08:29:59 CEST 2009
Aleksey Bader <bader at newmail.ru> writes:
I've remembered that I'd got an idea of decreasing fft threshold if length
of multipliers significantly differs. Assume we multiply 2 numbers u and v,
with length n ? m correspondingly. Let's fix n>m. In that case we usually
make 3*fft(n+m). 3 - because we need to find u image, v image and recover
u*v via inverse fft.
If n/m is big enough then 3*fft(n+m) could be replaced with
(2*n/m+1)*fft(2m) (I can't say how big should be n/m, maybe 3-4 goes well).
Even for the very unbalanced case (n >> m) there is no need to split the
two operands in equal parts. Instead split the larger operand into such
pieces that the partial products fit well inte a transform size.
Or, use mixed-degree Toom, as suggested by Niels in his reply.
Obviously, fft threshold for equal-order numbers won't change, but it could
be less in the case described above.
Even if it does not seems to be practical, that approach might be useful
when number/vector/matrix is multiplied by vector/matrix.
Is it something you have already done? If so, is it profitable?
Absolutely. In general, the potential for speedups when we have
invariance is greater for small primes FFT than for the
large-coefficient Schönhage-Strassen.
Also I noticed that FFT multiplication is planned to be completely rewritten
(http://gmplib.org/#FUTURE).
Which method will be used? The new SS approach from Paul Zimmermann,
Pierrick Gaudry and Alexander Kruppa or the approach from Tommy Färnqvist
and Niels Möller?
We have lots of new FFT code, and are working along different lines.
--
Torbjörn
More information about the gmp-devel
mailing list