public class FFT { //Uses Cooley-Tukey Algorithm public static ComplexNumber findFFT(double[] data,int k) { //recursive function if (data.length==1) { //base case return new ComplexNumber(data[0]); } double[] dataE=new double[data.length/2]; double[] dataO=new double[data.length/2]; for (int i=0;i<data.length;i++) { //radix-2 if (i%2==0) { dataE[i/2]=data[i]; } else dataO[i/2]=data[i]; } if (k<data.length/2) { //recurse return findFFT(dataE,k).add(findFFT(dataO,k).mult(new ComplexNumber(Math.cos(-2*k*Math.PI/data.length),Math.sin(-2*k*Math.PI/data.length)))); } k-=data.length/2; return findFFT(dataE,k).add(findFFT(dataO,k).mult(new ComplexNumber(Math.cos(-2*k*Math.PI/data.length),Math.sin(-2*k*Math.PI/data.length)))); } public static double[] getFFT(double[] data) { //data length is a power of 2 double[] fft=new double[data.length]; for (int i=0;i<fft.length;i++) { //evaluate all of the points System.out.println(data.length-i); fft[i]=findFFT(data,i).abs(); } return fft; } }

public class ComplexNumber { double real; double imaginary; public ComplexNumber() { real=0; imaginary=0; } public ComplexNumber(double d) { real=d; imaginary=0; } public ComplexNumber(double r, double i) { real=r; imaginary=i; } public ComplexNumber add(ComplexNumber other) { return new ComplexNumber(real+other.real,imaginary+other.imaginary); } public ComplexNumber mult(ComplexNumber other) { return new ComplexNumber(real*other.real-imaginary*other.imaginary,real*other.imaginary+imaginary*other.real); } public double abs() { return Math.sqrt(real*real+imaginary*imaginary); } public String toString() { return ""+real+""+imaginary+"i"; } }

A third class is used to generate a vector of numbers:

double[] time=new double[8192]; double[] signal=new double[8192]; for (int i=0;i<time.length;i++) { time[i]=i/4096.0; signal[i]=2*Math.sin(2*Math.PI*time[i]); }

This should in theory, give a bunch of 0's, and one 2, when I call the FFT.getFFT method, but it doesn't. The source for my algorithm is http://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm#The_radix-2_DIT_case

So I'm not sure if it's a small coding error, or if I completely misread the algorithm. Is there anything wrong with the code?