fft.cpp

fft shuzi xinhao chuli fft kuaisu傅里叶变换程序

#include<iostream.h>
#include<math.h>
#ifndef xushuclass
#define xushuclass
//template<class t>
class xushu //定义一个虚数类，为后面准备
{
public:
float x;
float y;
xushu(float a=NULL,float b=NULL)
   {
    x=a;
    y=b;
   }
void operator=(xushu m)
{
   x=m.x;
   y=m.y;
   return;
}
   bool operator==(xushu m)
   {
    if((x==m.x)&&(y==m.y))
     return true;
    return false;
   }
   xushu operator+(xushu m)
   {
    xushu temp;
    temp.x=x+m.x;
    temp.y=y+m.y;
    return temp;
   }
   xushu operator-(xushu m)
   {
    xushu temp;
    temp.x=x-m.x;
    temp.y=y-m.y;
    return temp;
   }
   xushu operator*(xushu m)
   {
    xushu temp;
    temp.x=x*m.x-y*m.y;
    temp.y=x*m.y+y*m.x;
    return temp;
   }
   xushu operator/(xushu m)
   {
    xushu temp;
    temp.x=(x*m.x+y*m.y)/(m.x*m.x+m.y*m.y);
    temp.y=(y*m.x-x*m.y)/(m.x*m.x+m.y*m.y);
    return temp;
   }
   xushu power(int n)//   n次方
   {
    xushu temp(1,0);
    xushu temp2(x,y);
    if(n==0)
     return temp;
    else if(n>0)
    {
     for(int k=1;k<=n;k++)
      temp=temp*temp2;
     return temp;
    }
    else
     return temp/power(-n);
   }
   };
#endif
#ifndef pi
#define pi 3.14159265   
#endif
//template<class t>
void fftsort(xushu*in,int k);//排序的function声明
void fft(xushu*inout,int i=0,int j=0) //算法主体,调用时i=0,j=n-1就可以了
//inout为传入的数组，从inout 的inout[i]到inout[j]运用蝶形算法分成
//两半，为inout[i]到inout[(i+j)/2],和inout[(i+j)/2+1]到inout[j]
//注意，这个数组还要排序才是最终结果
{
if(j<=i) //每个数组只有1个数了，可以了
   return;
int num=j-i+1;
xushu *temp=new xushu[num]; //temp为中间变量
xushu w((float)cos(pi*2/num),(float)sin(pi*2/num));//系数
int k;
for(k=0;k<num/2;k++) //变换主体
{
   temp[k]=inout[i+k]+inout[i+k+num/2];
   temp[k+num/2]=(inout[i+k]-inout[i+k+num/2])*w.power(k);
}
for(k=0;k<num;k++)//从temp传回来
   inout[i+k]=temp[k];
fft(inout,i,(i+j)/2); //显然，这两句是递归
fft(inout,(i+j)/2+1,j);//运用蝶形算法，直到j<=i
k=0;
while(pow(2,k)<j-i+1)
k++;
fftsort(inout,k);//算法最捂得出的并非是最终数组，而要排一次序
//排序的function在下面
}
void fftsort(xushu*in,int k)//这个function用来对最后的数列排序
//但还有些问题，故下面没用
{
int n=(int)pow(2,k);
int t=0,next=0;
bool*changed=new bool[n];
for(int pre=0;pre<n;pre++)//标记数组的元素是否已排序
changed[pre]=false;
for(pre=0;pre<=n-1;pre++)
{
   next=0;
   int tem=pre;
   for(int count=1;count<=k;count++)//用数组下标用k进制数表示，
//倒过来就是它该放的位置了
   {
    t=tem%2;
    next=next*2+t;
tem=(tem-t)/2;
   }
   if(!changed[pre])//没排序的排序
   {
    xushu temp;
    temp=in[pre];
    in[pre]=in[next];
    in[next]=temp;
    changed[pre]=true;
    changed[next]=true;
   }
}
   delete changed;
}

//以下为调用实例

void main()
{
xushu inout[8];
for(int k=0;k<8;k++)
{
   inout[k].x=(float)(5.1+k/2-k*k/10);
   inout[k].y=0;
}
fft(inout,0,7);//调用fft
for(k=0;k<8;k++)
{
   cout<<inout[k].x<<' '<<endl;//第一个量较大，其余较小就对了
   cout<<inout[k].y<<endl;
}
cout<<endl;
}