Question

谁能给一个C语言的FFT算法程序啊，急用

Answer 1

typedef struct complex_struct
{
float real;
float img;
} complex;
void FFT(complex *TD,complex *FD,int r)
{
int count;
int i,j,k;
int bfsize,p;
float angle;
complex *W,*X1,*X2,*X;
W=w; X1=x1; X2=x2;
count=1<<r;
for ( i=0;i<count/2;i++ )
{
angle=-i*PI*2/count;
(W+i)->real=cos(angle);
(W+i)->img=sin(angle);
}
for ( i=0;i<count;i++ )
{
(X1+i)->real=(TD+i)->real;
(X1+i)->img=(TD+i)->img;
}
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)->real=(X1+i+p)->real+(X1+i+p+bfsize/2)->real;
(X2+i+p)->img=(X1+i+p)->img+(X1+i+p+bfsize/2)->img;
(X2+i+p+bfsize/2)->real=((X1+i+p)->real-(X1+i+p+bfsize/2)->real)
*(W+i*(1<<k))->real-((X1+i+p)->img -(X1+i+p+bfsize/2)->img)*(W+i*(1<<k))->img;
(X2+i+p+bfsize/2)->img=((X1+i+p)->real-(X1+i+p+bfsize/2)->real)
*(W+i*(1<<k))->img+((X1+i+p)->img -(X1+i+p+bfsize/2)->img)*(W+i*(1<<k))->real; }
}
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)->real=(X1+p)->real;
(FD+j)->img=(X1+p)->img;
}
}

Answer 2

C++要不要

Answer 3

傅里叶变换？