recursive to iterative mpn/mul_fft?

[Sven Bettscheider]

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