fft1.cpp

一种混合高速的FFT算法 可以快速计算高阶FFT

// FFT1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "FFT.h"

double fftTime(int ll,int s);
double fftLeak(int ll,int s);
double timeUsed(struct _timeb *start);


int main(int argc, char* argv[])
{
	double          t, p;
    int            i, n, l;
    int            nmax, nfft[100];  
	
	
	cout<<"\nMixFFT Test";  
	do {
		cout<<"\n\n"
			<<"0\t\tExit.\n"
			<<"1\t\tExample. FFT lengths : 128,256,512,...8192/ \n"
			<<"2\t\tExample. 5 random FFT lengths.\n"
			<<"3\t\tUser selectable FFT length.\n\n"
			<<"Enter selection, 0-3 : ";
		cin>>n;
		nmax = 0;
		switch(n) {
		case 0 : nmax = 0; break;
		case 1 :
			nmax = 7;
		    nfft[0]  =  128;
			nfft[1]  =  256;
			nfft[2]  =  512;
			nfft[3]  = 1024;
			nfft[4]  = 2048;
			nfft[5]  = 4096;
			nfft[6]  = 8192;
			break;
		case 2 : 
			nmax = 5;
			for(i=0;i<nmax;i++){
				nfft[i]=rand()%500+2;
			}
			break;
		case 3 : 
			cout<<"\nEnter FFT length, 0 < length <= "<<maxIndex<<", maxPrime <= "<<maxPrimeFactor;
			cin>>l;
			if ((l > 0) && (l <= maxIndex)) 
			{
				nfft[0] = l;
				nmax = 1;
			}
			else cout<<"The length must satisfy: 0 < length <=  "<<maxIndex<<"!"<<endl;
	
			break;
		}
		for (i=0; i<nmax; i++) 
		{
			t = fftTime(nfft[i],0);
			p = fftLeak(nfft[i],0);
			cout<<"\n "<<nfft[i]<<" \t"<<t<<" s\t"<<p<<" dB"<<endl;
		}  

	} while(n >0);

	return 0;
}
double fftTime(int ll, int style)
{
    int            i, k, n, m, q;  
    double         w, re[maxIndex], im[maxIndex];
    double         elapsed_time;
    struct _timeb  start;

	
	n=ll;
    k  = 1;
    w  = k*(pi)/n/n;

    for (i=0; i<n; i++) {
        re[i] = cos(i*i*w);
        im[i] = sin(i*i*w);
    }      
	
	FFT one(ll,re,im);
    m = 0;
    q = 1;            
    _ftime(&start);
    while (timeUsed(&start) < 2.0)
    {
        for (i=0; i<q; i++)
			one.fft();
		
        m = m + q;
        q = q + q;
    }
    elapsed_time = timeUsed(&start)/(double)m;
    return(elapsed_time);
}


double fftLeak(int ll,int style)
{
    int            i, k, n;  
    double          w, re[maxIndex], im[maxIndex];
	
    n = ll;                             
    k = 3;
    w = 2*k*(pi)/n;
    for (i=0; i<n; i++) {
        re[i] = cos(i*w);
        im[i] = sin(i*w);
    }     
	FFT one(ll,re,im);
	one.fft();
	return (one.leak());

}
double timeUsed(struct _timeb *start)
{                               
    double seconds;
    struct _timeb   finish;
	
    _ftime(&finish);
    seconds = (double) finish.millitm;
    seconds = seconds - start->millitm;
    seconds = seconds / 1000;
    seconds = seconds + finish.time - start->time;
    
    return(seconds);
}