Recursive FFT java implementation

Question

Given below is my java program for FFT. For the input {0,2,3,-1} its returns a false output in complex point representation.

 import java.io.*;
 public class test{
static double s[]={0,2,3,-1};
static double[][] re=new double[s.length][2];
static double[][] er=new double[s.length][2];
static double[][][] ma=new double[s.length][s.length][2];
public static void main(String args[])
{
    double[][] aray1=new double[s.length][2];
    for(int i=0;i<s.length;i++)
    {
        aray1[i][0]=s[i];
        aray1[i][1]=0;
    }
    re=fft(aray1,1);
    for(int i=0;i<re.length;i++)
    {
        System.out.println(""+re[i][0]+"+i*"+re[i][1]);
    }
            //Inverse FFT
    re=fft(re,-1);
    for(int i=0;i<re.length;i++)
    {
        //System.out.println("sdsfbv /n /n");
        System.out.println(""+(re[i][0]/s.length)+"+i*"+((re[i][1])/s.length));
    }


}
public static double[][] complexmult(double[][] a,double[][] b)
{
    double[][] e=new double[1][2];

    return e;
}
public static double[][] fft(double[][] a, int c)
{
    double[][] de=new double[1][2];
    int n=a.length;

    if(n==1)
    {
        return a;
    }
    double wnx=Math.cos(c*2*Math.PI/n);
    double wny=Math.sin(c*2*Math.PI/n);
    double wx=1;
    double wy=0;
    double[][] y=new double[n][2];
    double[] e=new double[n];
    double[][] a0=new double[n/2][2];
    double[][] a1=new double[n/2][2];
    double[][] y0=new double[n][2];
    double[][] y1=new double[n][2];
    for(int i=0,k=0,j=0;i<n;i=i+1)
    {
        if((i%2)==0)
        {

            a0[k][0]=a[i][0];
            a0[k][1]=a[i][1];
            k=k+1;
        }
        else
        {

            a1[j][0]=a[i][0];
            a1[j][1]=a[i][1];
            j=j+1;
        }
    }
    y0=fft(a0,c);
    y1=fft(a1,c);       
    for(int k=0;k<=((n/2)-1);k++)
    {
        double m1=((wx*y1[k][0])-(wy*y1[k][1]));
        double m2=((wx*y1[k][1])+(wy*y1[k][0]));
        y[k][0]= y0[k][0]+m1;
        y[k][1]=y0[k][1]+m2;
        y[k+(n/2)][0]=y0[k][0]-m1;
        y[k+(n/2)][1]=y0[k][1]-m2;
        wx=((wx*wnx)-(wy*wny));
        wy=((wx*wny)+(wy*wnx));
    }
    return y;       
}
}

Output is as follows:

    4.0+i*0.0
    -3.0+i*1.8369701987210297E-16
    2.0+i*0.0
    -3.0+i*-1.8369701987210297E-16

Please trace the program and help me where i am making a mistake?

Answer 1

The problem is in these two lines:

    wx=((wx*wnx)-(wy*wny));
    wy=((wx*wny)+(wy*wnx));

You are clobbering the value of wx by replacing it with the new one in the first line before using it to compute the new value of wy in the second line. So, the result of the complex multiplication is not correct. Also, although this is not causing the error, there is no need to initialize y0 and y1 since they are set by the recursive calls to fft. There are also other unused variables.