fft interface

Torbjorn Granlund tg at gmplib.org
Fri Oct 19 10:52:37 CEST 2012

We envision invariance for multiplication for almost all operand sizes
and for division for all operand sizes.

We have made some experiments with the implicit multiplication
invariance of a very unbalanced a * b, i.e., where log a >> log b.
Alberto Zanoni might have published something in this area for Karatsuba
and Toom.

I believe Niels Möller made some experiments with saving a "transform"
from a recursive chain of Toom.

IIRC, we saw speedups worth pursuing.

For FFT the wins are greater, but with Schönhage-Strassen's (SS) algorithm
mod 2^2^k+1 the savings are not great, as the main work is not in the
transforms, but in the pointwise coefficient multiplies of transformed
polynomials.  Algorithm variants with "small coefficients" (and thus
slower multiplication by roots-of-unity) are better.

When we merge the small primes (SP) FFT (which is of the latter variety)
we expect to get a cutoff point from SS FFT to SP FFT when there is no
invariance, and a much lower one (perhaps 0) when there is invariance.

And yes, we would like to support addition at the transform side of
things.  It is not clear how to define things as to avoid overflow,


More information about the gmp-devel mailing list