I'm currently trying to implement the FFT algorithm in java and am having a bit of trouble with it! I've tested all other parts of the algorithm well and they seem to be working fine.
The trouble I'm getting is that in the base case it returns a Complex number array, within the base case A[0]
is populated. After the base cases have been executed, the for loop is executed where y0[0]
and y1[0]
are found to be null, despite assigning them to the base cases, pretty confused by this. This is shown in the System.out.println
line
Can anyone tell me the errors of my ways?
//This method implements the recursive FFT algorithm, it assumes the input length
//N is some power of two
private static Complex[] FFT(Complex[] A, int N) {
double real, imag;
Complex A0[] = new Complex[((int) Math.ceil(N/2))];
Complex A1[] = new Complex[((int) Math.ceil(N/2))];
Complex[] omega = new Complex[N];
Complex[] y = new Complex[N];
Complex[] y0 = new Complex[((int) Math.ceil(N/2))];
Complex[] y1 = new Complex[((int) Math.ceil(N/2))];
//base case
if (N == 1) {
return A;
}
else {
real = Math.cos((2*Math.PI)/N); if (real < 1E-10 && real > 0) real = 0;
imag = Math.sin((2*Math.PI)/N); if (imag < 1E-10 && imag > 0) imag = 0;
omega[N-1] = new Complex(real, imag);
omega[0] = new Complex(1, 0);
A0 = splitInput(A, 1);
A1 = splitInput(A, 0);
//recursive calls
y0 = FFT(A0, N/2);
y1 = FFT(A1, N/2);
for (int k = 0; k < ((N/2)-1); k++) {
System.out.print("k: " + k + ", y0: " + y0[k]); System.out.println(", y1: " + y1[k]);
y[k] = y0[k].plus(omega[k].times(y1[k]));
y[k+(N/2)] = y0[k].minus(omega[k].times(y1[k]));
omega[0] = omega[0].times(omega[N]);
}
return y;
}
}
Here is the code for my splitInput method as requested
//This method takes a double array as an argument and returns every even or odd
//element according to the second int argument being 1 or 0
private static Complex[] splitInput(Complex[] input, int even) {
Complex[] newArray = new Complex[(input.length/2)];
//Return all even elements of double array, including 0
if (even == 1) {
for (int i = 0; i < (input.length/2); i++) {
newArray[i] = new Complex(input[i*2].re, 0.0);
}
return newArray;
}
//Return all odd elements of double array
else {
for (int i = 0; i < (input.length/2); i++) {
newArray[i] = new Complex (input[(i*2) + 1].re, 0.0);
}
return newArray;
}
}
EDIT: I've updated my code according to your suggestions, still getting a null pointer exception from the line y[k] = y0[k].plus(omega[k].times(y1[k]));
as y0
& y1
are still null
after the base case :( any further ideas? Here's the updated algorithm
//This method implements the recursive FFT algorithm, it assumes the input length
//N is some power of two
private static Complex[] FFT(Complex[] A, int N) {
double real, imag;
Complex[] omega = new Complex[N];
Complex[] y = new Complex[N];
Complex[] A0;
Complex[] A1;
Complex[] y0;
Complex[] y1;
//base case
if (N == 1) {
return A;
}
else {
real = Math.cos((2*Math.PI)/N); if (real < 1E-10 && real > 0) real = 0;
imag = Math.sin((2*Math.PI)/N); if (imag < 1E-10 && imag > 0) imag = 0;;
omega[N-1] = new Complex(real, imag);
omega[0] = new Complex(1, 0);
A0 = splitInput(A, 1);
A1 = splitInput(A, 0);
//recursive calls
y0 = FFT(A0, N/2);
y1 = FFT(A1, N/2);
for (int k = 0; k < ((N/2)-1); k++) {
y[k] = y0[k].plus(omega[k].times(y1[k]));
y[k+(N/2)] = y0[k].minus(omega[k].times(y1[k]));
omega[0] = omega[0].times(omega[N-1]);
}
return y;
}
}
Problems that jump out:
(int) Math.ceil(N/2)
You're still doing an int
division, so the Math.ceil()
has no effect, and your split arrays are probably incorrect for odd n
omega[0]
and omega[N-1]
, I would expect a NullPointerException
when you try to access omega[1]
, which would happen when N >= 6
.omega[N]
, as also mentioned by sarnoldA0
and A1
, and later assign them the results of splitInput