# recursive to iterative mpn/mul_fft?

Sven Bettscheider Sven.Bettscheider at gmx.de
Fri Aug 12 11:06:48 CEST 2011

```In function mpn_fft_fft(...)

if (K == 2){...}
else
{
int j;
int *lk = *ll;
mpn_fft_fft (Ap,     K >> 1, ll-1, 2 * omega, n, inc * 2, tp);
mpn_fft_fft (Ap+inc, K >> 1, ll-1, 2 * omega, n, inc * 2, tp);
/* A[2*j*inc] <- A[2*j*inc] + omega^l[k][2*j*inc] A[(2j+1)inc]
A[(2j+1)inc] <- A[2*j*inc] + omega^l[k][(2j+1)inc]
A[(2j+1)inc] */

}

Is it possible to implement the red lines with using a loop (while, for)?

Am 10.08.2011 19:15, schrieb Torbjorn Granlund:
> Sven Bettscheider<Sven.Bettscheider at gmx.de>  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
> iteratively.
>
> 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.
>

--
B. Sc. Sven Bettscheider
Augustinusstraße 35
66571 Wiesbach

Sven.Bettscheider at gmx.de
06806/869135

```