FFT { public Complex[] fft(Complex[] x) { int N = x.length; Complex[] y = new Complex[N]; if (N == 1) { y[0] = x[0]; return y; } if (N % 2 != 0) throw new RuntimeException("N is not a power of 2"); Complex[] even = new Complex[N / 2]; Complex[] odd = new Complex[N / 2]; for (int k = 0; k < N / 2; k++) even[k] = x[2 * k]; for (int k = 0; k < N / 2; k++) odd[k] = x[2 * k + 1]; Complex[] q = fft(even); Complex[] r = fft(odd); 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; }  Complex[] fft(Complex[] x); static void show(Complex[] x, String title);  }
@Test public void testFft() { System.out.println("fft"); Complex[] s = new Complex[8192]; for (int i = 0; i < s.length; i++) { s[i] = new Complex(0,0); } Complex[] r = fft.fft(s); r = fft.fft(s); long st = System.nanoTime(); r = fft.fft(s); long f = System.nanoTime(); System.out.println("Duration=" + (f-st)); }