FFT functions

[Paul Underwood]

>
> 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?
> 

Operands will start out very small but rapidly grow due to exponentiation.
I suppose, programmatically, we could pass an argument for the maximum
size needed -- rounded up. This might make things easy to implement?

Best Wishes

Paul