C语言实现FFT基二算法详解

C编写的时域基2抽取的FFT算法程序2008年07月21日 星期一 10:39kkfft(pr,pi,n,k,fr,fi,l,il)函数说明：
pr[n]：输入的实部 
pi[n]：数入的虚部 
n，k：满足n=2^k 
fr[n]：输出的实部/模 
fi[n]：输出的虚部/幅角
l：0 FFT，1 IFFT 
il：0 输出按实部/虚部；1 输出按模/幅角

源程序如下：

#include "stdio.h"

#include "math.h"


void kkfft(pr,pi,n,k,fr,fi,l,il)

int n,k,l,il;

double pr[],pi[],fr[],fi[];

{   int it,m,is,i,j,nv,l0;

    double p,q,s,vr,vi,poddr,poddi;

    for (it=0; it<=n-1; it++)

      { m=it; is=0;

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

          { j=m/2; is=2*is+(m-2*j); m=j;}

        fr[it]=pr[is]; fi[it]=pi[is];

      }

    pr[0]=1.0; pi[0]=0.0;

    p=6.283185306/(1.0*n);

    pr[1]=cos(p); pi[1]=-sin(p);

    if (l!=0) pi[1]=-pi[1];

    for (i=2; i<=n-1; i++)

      { p=pr[i-1]*pr[1]; q=pi[i-1]*pi[1];

        s=(pr[i-1]+pi[i-1])*(pr[1]+pi[1]);

        pr[i]=p-q; pi[i]=s-p-q;

      }

    for (it=0; it<=n-2; it=it+2)

      { vr=fr[it]; vi=fi[it];