recursive to iterative mpn/mul_fft?

Torbjorn Granlund tg at
Wed Aug 10 19:15:36 CEST 2011

Sven Bettscheider <Sven.Bettscheider at> writes:

  Is it possible to change the following functions So that they work
  iteratively rather than recursively?
I am not sure I follow you.  These functions compute the FFT transforms

The addition, subtraction, and multiplies by roots-of-unity are done
using function calls, which are not in themselves calling the
transformation functions.

The dyadic product done when the transforms are ready is done with
either general multiplication (for small operands), or with recursion to
FFT (for large operands).  So the dyadic products make the entire FFT
multiply code recursive.


More information about the gmp-discuss mailing list