Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.