fft1.cpp

用visual c++6.0编写的 FFT程序

#include "stdafx.h"
#include "iostream.h"
#include "math.h"

#define  pi  3.141592653

struct  MultiNumber
{
	double real;
	double imag;
};

MultiNumber ComMultiply(MultiNumber x , MultiNumber y)
{
	MultiNumber a;

    a.real = x.real*y.real - x.imag*y.imag;

    a.imag = x.real*y.imag + x.imag*y.real;

	return a;
}

MultiNumber ComAdd(MultiNumber x , MultiNumber y)
{
	MultiNumber a;

	a.real = x.real + y.real;

	a.imag = x.imag + y.imag;

	return a;
}

MultiNumber W(int m , int k)
{
	MultiNumber a;

    double b = pow(2,double(m-1));

	double c = double(k%(int(b)));

	b = pow(2,m);

	a.real = cos(2*pi*c/b);

	a.imag = (-1)*sin(2*pi*c/b);

	return a;
}

 MultiNumber static one = {-1,0};



int GetRest(int v , int k , int m)

{
	int rest =0;

	int t1 = 0;

	int t2 = 0;

	int t3 = 0;

	int k1 = k;

	for(int d = 1 ; d<=m-1 ; d++)

	{
		t1 = int(pow(2 , double(v-d)));

		t2 = int(pow(2 , double(d-1)));

        t3 = k/t1;
 
        rest = t3*t2+rest;

		k = k - t1*(t3);


	}

	return rest;

}



int rest =0;

int k =0;

MultiNumber *FFT(int v , MultiNumber *h)

{

int static N = int(pow(2,double(v)));

int step = 1;

MultiNumber a ,b;

for(int m = 1; m<=v ; m++)

{


step = int(pow(2 , double(v-m)));

for(  int i = 0 ; i<N-step  ; i = i + step*2)

{   

	for(k=i; k<=i+step-1 ; k++ )

{

	a = ComAdd(h[k+0] , ComMultiply(h[k+step] , W(m,GetRest(v,k,m))));

	b = ComAdd(h[k+0] , ComMultiply(h[k+step] ,ComMultiply(one, W(m,GetRest(v,k,m)))));

	h[k+0] = a;

	h[k+step] = b;

    
}

}

}

return h;



}

int InverseBit(int k , int v)

{

	int t = 1;

	int t1 =1;

	int k1 = k;

	int result = 0;

for(int i=v-1 ; i>=0 ; i--)

{

  t = int(pow(2,i));

  t1 = int(pow(2,v-i-1));

  result = result + (k1/t)*t1;

  k1 = k1 - (k1/t)*t;

}

return result;

}


MultiNumber *GetLastRe(MultiNumber *h , int v)

{
    int y = 0;

	int N = int(pow(2,v));

	MultiNumber *h1 = new MultiNumber[N];

	for(int i=0 ; i<N ; i++)

	{

        y = InverseBit(i,v);

        h1[i] = h[y];

	}

	return h1;

}



int main()
{   


	int m = 5;
    
	int N = int(pow(2, m));

	MultiNumber *a = new MultiNumber[N];
////////////////////////////2008.12.22李琳
		FILE* stlfp;
		CString fileName;
// 		int i=0,j=0,cnt=0 ,pCnt=4;
		int line=0;
		char readline[100];
		double x=0;
		fileName="J:\006modify.txt";
		stlfp = fopen(fileName,"r");
		if(!stlfp)
			return false;
		else
		{
			do
			{
				fgets(readline,100,stlfp);

// 				while(a[i]!='\0')
// 				{
// 					str[j]=a[i];
// 					j++;
// 				}
// 				str[j]='\0';
// 				j=0;
// 				if(sscanf(str,"%lf%lf%lf",&x,&y,&z)==3)
// 				{
// 					tPoint.SetParam(x,y,z);
// 					pointList->Append(tPoint);
// 				}
				a[line].real = atoi(readline);
				a[line].imag = 0;

			}while(!feof(stlfp));
			fclose(stlfp);
		}

//////////////////////////////2008.12.22李琳

//     for(int i=0 ; i<N ; i++)
// 	{
// 
// 	a[i].real = i;
// 	a[i].imag = 0;
// 
// 	}
    

 


MultiNumber *b = FFT(m,a);



b = GetLastRe(b,m);
 
 for( int i =0 ; i<N ; i++)

 {

	 cout<<b[i].real<<"  "<<b[i].imag<<endl; 

 }



	return 0;
}