快速傅里叶变换

用2FFT实现快速傅里叶，貌似不少大大都玩过，传说某些神一般的任务已经把离散信号的快速傅里叶变换的时间复杂度压缩到一个很吓人的地步了~

今天ooxx研究院给大家带来一段用2FFT实现的快速傅里叶变换，渣代码。高手飘吧

流程图就不贴了，反正就那么回事

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#define pi 3.14159265357
struct st
{
    double re;
    double im;
    };
st x[1000];
double mod[1000];
void FFT(int M)
{
    
    int L;
    int N=1<<M;
    int LH=N/2;
    int J=LH;
    int N1=N-2;
    double w,p=0;
    for(int i=1;i<=N1;i++)
    {
        if(i<J)
        {
                st temp;
                temp=x[i];
                x[i]=x[J];
                x[J]=temp;
        }
        int K;
        K=LH;
        while(J>=K)
        {
            J-=K;
            K/=2;
            
        }
            J+=K;
        
    }

        int B;
        for(L=1;L<=M;L++)
        {
            B=1<<(L-1);
            for(J=0;J<=B-1;J++)
            {
                p=(1<<(M-L))*J;
            
                 w=(2*pi*1.0/N)*p;
                
                for(int k=J;k<=N-1;k+=1<<L)
                {
                    st temp;
                    temp.re=x[k].re+x[k+B].re*cos(w)+x[k+B].im*sin(w);
                    temp.im=x[k].im+x[k+B].im*cos(w)-x[k+B].re*sin(w);
                     x[k+B].re=x[k].re-(x[k+B].re*cos(w)+x[k+B].im*sin(w));
                     x[k+B].im=x[k].im-(x[k+B].im*cos(w)-x[k+B].re*sin(w));
                     x[k].re=temp.re;
                     x[k].im=temp.im;
                }
            }
            
         }
    }
    int main()
    {
        int n,m,i,j;
        while(scanf("%d",&n))
        {
            memset(x,0,sizeof(x));
            for(i=0;i<=n-1;i++)
            scanf("%lf",&x[i].re);

            i=n;
            m=0;
            while(i>0)
            {
                i/=2;
                m++;
                }
            
            FFT(m);
            for(i=0;i<=n-1;i++)
             {
                    mod[i]=sqrt(x[i].re*x[i].re+x[i].im*x[i].im);
                    
                   
                    printf("%.4lf+%.4lfi  ",x[i].re,x[i].im);
                }
                printf("\\n");
                 
        }
        return 0;
}

Xushine

484