wrong with my FFT program

hi,all.I wrote this program to implement the FFT algorithm.Running with wrong answer.can anybody tell me what mistake i made?thanks!

Code:

---

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

#define PI 3.1415926
#define N 16 //the length
#define W_RE (cos(-2.0*PI/N))
#define W_IM (sin(-2.0*PI/N))

void recursive_fft(double [],int,double [],double []);

int main(){

        double x[N] = {0.5751,0.4514,0.0439,0.0272,
                                  0.3127,0.0129,0.3840,0.6831,
                            0.0928,0.0353,0.6124,0.6085,
                            0.0158,0.0164,0.1901,0.5869};
        double y_re[N],y_im[N];

        recursive_fft(x,N,y_re,y_im);

        /*output*/
        for(int i = 0;i<N;i++){
                printf("%lf",y_re[i]);
                if(y_im[i])
                        printf(" + %lfi",y_im[i]);
        printf("\n");
        }
        return 0;
}

/*x is the input DFT，len_x is the length
 *y_re and y_im ===> real part and image part of the result
 * */
void recursive_fft(double x[],int len_x,\
                                                double y_re[],double y_im[]){

        double re_w = 1.0,im_w = 0;
        double x_even[len_x/2],x_odd[len_x/2];
        double y1_re[len_x/2] ,y1_im[len_x/2] ;
        double y2_re[len_x/2] ,y2_im[len_x/2] ;
        int index_even = 0,index_odd = 0;

        for(int i=0;i<len_x/2;i++){
            y1_re[i] = y1_im[i] = y2_re[i] = y2_im[i] = 0;
    }
        if(1 == len_x){
                y_re[0] = x[0];y_im[0] = 0;
                return ;
        }

       
        for(int i = 0;i<len_x;i++){
                if(i % 2 == 0){/*even */
                        x_even[index_even++] = x[i];
                }else{
                        x_odd[index_odd++] = x[i];
                }
        }

        recursive_fft(x_odd,index_odd,y1_re,y1_im);
        recursive_fft(x_even,index_even,y2_re,y2_im);

        for(int k = 0;k<len_x/2;k++){
                y_re[k] = y1_re[k]*re_w - im_w*y1_im[k] + y2_re[k];
                y_im[k] = y1_im[k]*re_w + y1_re[k]*im_w + y2_im[k];
                y_re[k+len_x/2] = im_w*y1_im[k] - y1_re[k]*re_w + y2_re[k];
                y_im[k+len_x/2] = -1*y1_im[k]*re_w - y1_re[k]*im_w + y2_im[k];
                re_w = re_w*W_RE - im_w*W_IM;
                im_w = im_w*W_RE + re_w*W_IM;
        }
}

---

any hint?

Assuming you're using Cooley-Tukey DIT (which is the best fit I could find on Wiki), it would seem that you're always using exp(-2πi/N), when that N should be changing with the recursion to be exp(-2πi/len_x).

Quote:

---

Originally Posted by tabstop

Assuming you're using Cooley-Tukey DIT (which is the best fit I could find on Wiki), it would seem that you're always using exp(-2πi/N), when that N should be changing with the recursion to be exp(-2πi/len_x).

---

thanks,I do use the Cooley-Tukey algorithm.I modified my code as you said,and the answer's still wrong,did u find any logical mistake in my code?

replace the code

Code:

---

re_w = re_w*W_RE - im_w*W_IM;
        im_w = im_w*W_RE + re_w*W_IM;

---

with

Code:

---

save_re = re_w;save_im = im_w;
                re_w = save_re*W_RE(len_x) - save_im*W_IM(len_x);
                im_w = save_im*W_RE(len_x) + save_re*W_IM(len_x);

---