NTT multiplication.

[Torbjorn Granlund]

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