FFT functions

[Torbjörn Granlund]

Paul Underwood <paulunderwood at mindless.com> writes:

  Our question is will the GMP team ever provide FFT functions:
  * forward_FFT
  * pointwise_mult
  * reverse_FFT
  ?

  We would then be able to do 3 forward transforms, 6 point-wise ops and
  6 inverse transforms.

It is an interesting proposal!  I believe this might have been
considered sometimes in he past, but without conclusion.

The current FFT code uses "big" coefficients for the polynomials, while
the polynomial degree is limited.  The transform-side pointwise
multiplies are therefore not O(n) for input sizes n.

More common FFT schemes use more-or-less fixed-size coefficients,
meaning that the pointwise multiplies are (very close to) O(n).

As a result, with the current schemes, the benefits achived by saving
the trasformed polynomials is not that great.

We have newer code which uses several word-sized compiled-in primes (3
to 5 IIRC, depending on operand sizes), which would allow for much
greater speeups.  Unfortunately, that code (written by me and Niels
Möller) is not yet ready, and it has not gotten our attention for 10
years.

A generic interface for saving transformed operands might not be
straightforward to design.  E.g., how should one handle operands of
different sizes?

-- 
Torbjörn
Please encrypt, key id 0xC8601622