cfft.cpp

fft蝶形算法的逆变换

#include <iostream.h>
#include <math.h>
#include <complex>
using namespace std;
typedef complex<double> Complex;


#define pi 3.14159265


int ifft(Complex *a,int cishu)
{
	Complex u,w,t;
	unsigned int n=1,num2,nml,k,le,lei,ip;
	double temp;
	n<<=cishu;
	
	Complex N;
	N=Complex(1.0/n,0);
	
	num2=n>>1;
	nml=n-1;
	int i=0;
	int j=0;
	for(i=0;i<nml;i++)
	{
		if(i<j)
		{
			t=a[j];
			a[j]=a[i];
			a[i]=t;
		}
		k=num2;
		while(k<=j)
		{
			j=j-k;
			k=k>>1;
		}
		j=j+k;
	}
	le=1;
	for(int m=1; m<=cishu;m++)
	{
		lei=le;
		le<<=1;
		u=Complex(1,0);
		temp=pi/lei;
		w=Complex(cos(temp),sin(temp));
		for(j=0;j<lei;j++)
		{
			for(i=j;i<n;i+=le)
			{
				ip=i+lei;
				t=a[ip]*u;
				a[ip]=a[i]-t;
				a[i]=a[i]+t;
			}
			u=u*w;
		}
	}
	for(i=0;i<n;i++)
	{
		a[i]=a[i]*N;
		//real(a[i])=real(a[i])/n;
		//imag(a[i])=imag(a[i])/n;
	}
	return 0;

};








void main()
{
	Complex input[8];
	for(int i=0;i<8;i++)
	{
		input[i]=i;
	}
	ifft(input,3);

	for(i=0;i<8;i++)
	{
		cout<<real(input[i])<<"+"<<imag(input[i])<<"i"<<endl;
	}


}