/**
 * JavaWorld: Real-time Java Application Development For Multi-core Systems.
 * This code is public domain.
 */
public class Test1 {

    static final int LOG2_N = 14;
    static final int N = << LOG2_N;
    static final int K = 16// Number of frames.

    public static void main(String[] argsthrows Exception {
        Complex[][] frames = new Complex[K][N];
        Complex[][] results = new Complex[K][N];
        for (int i = 0; i < K; i++) {
            for (int j = 0; j < N; j++) {
                frames[i][jnew Complex(Math.random(), Math.random());
            }
        }
        long max = 0, sum = 0;
        final int n = 1000;
        for (int i = 0; i < n; i++) {
            Thread.sleep(5)// To limit garbage flow.
            long time = System.nanoTime();
            fft(frames[i % K], results[i % K]);
            time = System.nanoTime() - time;
            // System.out.println(time / 1000000.0); // Milliseconds.
            if (time > max) {
                max = time;
            }
            sum += time;
        }
        System.out.println("Maximum Execution Time: " (max / 1000000.0" ms");
        System.out.println("Average Execution Time: " (sum / n / 1000000.0" ms");
    }

    static void fft(Complex[] a, Complex[] A) {
        for (int i = 0; i < N; ++i) {
            A[reverseBits(i)] = a[i];
        }
        for (int s = 1; s <= LOG2_N; ++s) {
            int m = << s;
            Complex w = new Complex(10);
            Complex wm = new Complex(Math.cos(* Math.PI / m), Math.sin(* Math.PI / m));
            for (int j = 0; j < m / 2; ++j) {
                for (int k = j; k < N; k += m) {
                    Complex t = w.times(A[k + m / 2]);
                    Complex u = A[k];
                    A[k= u.plus(t);
                    A[k + m / 2= u.minus(t);
                }
                w = w.times(wm);
            }
        }
    }

    static int reverseBits(int x) {
        int n = 0;
        for (int i = 0; i < LOG2_N; i++) {
            n <<= 1;
            n |= (x & 1);
            x >>= 1;
        }
        return n;
    }

    static class Complex {

        double _real, _imag;

        Complex(double real, double imag) {
            _real = real;
            _imag = imag;
        }

        Complex plus(Complex that) {
            return new Complex(this._real + that._real, this._imag + that._real);
        }

        Complex minus(Complex that) {
            return new Complex(this._real - that._real, this._imag - that._real);
        }

        Complex times(Complex that) {
            return new Complex(this._real * that._real - this._imag * that._imag,
                    this._real * that._imag + this._imag * that._real);
        }
    }
}