一维的FFT和IFFT代码

#include "stdafx.h" #include "FFT_IFFT.h"//头文件进行申明 using namespace std; //要加上这个，不然还是无法识别complex类 #include "complex" //要用到complex类型的数据 #define PI 3.1415926 /************************************************************************* * * Function: FFT(conmplex<double>* TD,complex<double>* FD,int r); * ************************************************************************/ void FFT(complex<double>* TD,complex<double>* FD,int r) { long count; int i,j,k; int bfsize,p; double angle; complex<double> *W, *X1, *X2, *X; count=1<<r; W=new complex<double>[count/2];//变换点数的一半 X1=new complex<double>[count]; X2=new complex<double>[count]; for(i=0; i<count/2; i++) { angle=-i*PI*2/count; W[i]=complex<double> (cos(angle), sin(angle)); } memcpy(X1, TD, sizeof(complex<double>) *count); for(k = 0; k < r; k++) { for(j = 0; j < 1 << k; j++) { bfsize = 1 << (r-k); for(i = 0; i < bfsize / 2; i++) { p = j * bfsize; X2[i + p] = X1[i + p] + X1[i + p + bfsize / 2]; X2[i + p + bfsize / 2] = (X1[i + p] - X1[i + p + bfsize / 2]) * W[i * (1<<k)]; } } X = X1; X1 = X2; X2 = X; } // 重新排序 for(j = 0; j < count; j++) { p = 0; for(i = 0; i < r; i++) { if (j&(1<<i)) { p+=1<<(r-i-1); } } FD[j]=X1[p]; } // 释放内存 delete W; delete X1; delete X2; } /************************************************************************* * * Function: IFFT(conmplex<double>* TD,complex<double>* FD,int r); * ************************************************************************/ void IFFT(complex<double>* FD,complex<double>* TD,int r) { long count; int i; int bfsize,p; double angle; complex<double> *X; count=1<<r; X=new complex<double>[count]; memcpy(X, FD, sizeof(complex<double>) *count); for(i=0; i<count; i++) { X[i]=complex<double>(X[i].real(), -X[i].imag()); } FFT(X, TD, r); for(i=0; i<count; i++) { TD[i]=complex<double>(TD[i].real()/count, -TD[i].imag()/count); } delete X; }