Java Programming

Hi everyone !

I have to programm a FFT distributed into threads, therefore I cannot use the standard Radix FFT Algrithm, because it's rekursiv. I'm trying to make this following algortihm iterativ, but im not able to do this :-(

    // compute the FFT of x[], assuming its length is a power of 2
    public static Complex[] fft(Complex[] x) {
        int N = x.length;

        // base case
        if (N == 1) return new Complex[] { x[0] };

        // radix 2 Cooley-Tukey FFT
        if (N % 2 != 0) { throw new RuntimeException("N is not a power of 2"); }

        // fft of even terms
        Complex[] even = new Complex[N/2];
        for (int k = 0; k < N/2; k++) {
            even[k] = x[2*k];
        }
        Complex[] q = fft(even);

        // fft of odd terms
        Complex[] odd  = even;  // reuse the array
        for (int k = 0; k < N/2; k++) {
            odd[k] = x[2*k + 1];
        }
        Complex[] r = fft(odd);

        // combine
        Complex[] y = new Complex[N];
        for (int k = 0; k < N/2; k++) {
            double kth = -2 * k * Math.PI / N;
            Complex wk = new Complex(Math.cos(kth), Math.sin(kth));
            y[k]       = q[k].plus(wk.times(r[k]));
            y[k + N/2] = q[k].minus(wk.times(r[k]));
        }
        return y;
    }

I have found this C implemented non rekursiv version of this FFT Algorithm, but im not a C proffesionell, so i failed again :-(

void FFT_calculate(complex* x, long N /* must be a power of 2 */,
        complex* X, complex* scratch, complex* twiddles) {
    int k, m, n;
    int skip;
    bool evenIteration = N & 0x55555555;
    complex* E, * D;
    complex* Xp, * Xstart;

    if (N == 1) {
        /* N == 1 is now a special case, not the end of the recursion! */
    	X[0] = x[0];
    	return;
    }

    E = x;

    for (n = 1; n < N; n *= 2) {
        Xstart = evenIteration? scratch : X;
        skip = N/(2 * n);
        /* each of D and E is of length n, and each element of each D and E is
        separated by 2*skip. The Es begin at E[0] to E[skip - 1] and the Ds
        begin at E[skip] to E[2*skip - 1] */
        Xp = Xstart;
        for(k = 0; k != n; k++) {
            for (m = 0; m != skip; ++m) {
                D = E + skip;
                *D = complex_mult(twiddles[k * skip], *D);
                *Xp = complex_add(*E, *D);
                Xp[N/2] = complex_sub(*E, *D);
                ++Xp;
                ++E;
            }
            E += skip;
        }
        E = Xstart;
        evenIteration = !evenIteration;
    }
}

Can anyone give me some advice to make this Java code not rekursiv ?

Thanks a lot !

Edited by: Sephiknight on Jun 6, 2008 6:13 AM