C语言实现FFT和IFFT

#include 
#include 
#include 
#define N 1000
/*定义复数类型*/
typedef struct{
double real;
double img;
}complex;

complex x[N] *W; /*输入序列变换核*/
int size_x=0;      /*输入序列的大小，在本程序中仅限2的次幂*/
double PI;         /*圆周率*/

void fft（）;     /*快速傅里叶变换*/
void ifft（）;
void initW（）;   /*初始化变换核*/
void change（）; /*变址*/
void add（complex complex complex *）; /*复数加法*/
void mul（complex complex complex *）; /*复数乘法*/
void sub（complex complex complex *）; /*复数减法*/
void divi（complex complex complex *）;/*复数除法*/
void output（）;

int main（）{
int imethod;                             /*输出结果*/
system（“cls“）;
PI=atan（1）*4;
printf（“Please input the size of x:\n“）;
scanf（“%d“&size_x）;
printf（“Please input the data in x[N]:\n“）;
for（i=0;i   scanf（“%lf%lf“&x[i].real&x[i].img）;
initW（）;
printf（“Use FFT（0） or IFFT（1）?\n“）;
scanf（“%d“&method）;
if（method==0）
   fft（）;
else
   ifft（）;
output（）;
return 0;
}

/*快速傅里叶变换*/
void fft（）{
int i=0j=0k=0l=0;
complex updownproduct;
change（）;
for（i=0;i< log（size_x）/log（2） ;i++）{   /*一级蝶形运算*/
   l=1<   for（j=0;j    for（k=0;k      mul（x[j+k+l]W[size_x*k/2/l]&product）;
      add（x[j+k]product&up）;
      sub（x[j+k]product&down）;
      x[j+k]=up;
      x[j+k+l]=down;
    }
   }
}
}

/*快速傅里叶逆变换*/
void ifft（）{
int i=0j=0k=0l=size_x;
complex updown;
for（i=0;i< （int）（ log（size_x）/log（2） ）;i++）{   /*一级蝶形运算*/
   l/=2;
   for（j=0;j