fft1.cpp

这是一个时域抽取计算fft的c++实现

#include "iostream.h"
#include "math.h"
#include "time.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()
{   
	clock_t start,end;

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

	MultiNumber *a = new MultiNumber[N];

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

	a[i].real = i;
	a[i].imag = 0;

	}
    

 
start = clock();

MultiNumber *b = FFT(m,a);

end = clock();

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

 {

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

 }

cout<<"time: "<<end-start<<endl;

	return 0;
}

/**************************************
耗时情况
12                   187
11                   78
10                   31
9                    15
8                    0
****************************************/