fft算法程序c语言实现

FFT算法（快速傅里叶变换）是一种高效的离散傅里叶变换算法，可以将一个长度为N的序列在O(NlogN)的时间内完成傅里叶变换。

其实现方式在C语言中可以使用递归或迭代的方式实现。递归方式实现代码如下：

void fft(double complex *x, int n)
{
if(n == 1) return;
double complex even[n/2], odd[n/2];
for(int i=0; i<n/2; i++)
{
even[i] = x[2*i];
odd[i] = x[2*i+1];
}
fft(even, n/2);
fft(odd, n/2);
for(int k=0; k<n/2; k++)
{
double complex t = cexp(-I*2*M_PI*k/n) * odd[k];
x[k] = even[k] + t;
x[k+n/2] = even[k] - t;
}
}

该函数的输入参数为一个复数数组x和其长度n，输出结果也存放在x中。在递归过程中，先将输入序列分为偶数位和奇数位两部分，对每部分继续递归求解傅里叶变换，然后将得到的结果进行合并得到最终的结果。

迭代方式实现代码如下：

void fft(double complex *x, int n)
{
int bit = log2(n);
for(int i=0; i<n; i++)
{
int k = 0;
for(int j=0; j<bit; j++)
{
k |= ((i>>j)&1) << (bit-1-j);
}
if(k>i)
{
double complex tmp = x[i];
x[i] = x[k];
x[k] = tmp;
}
}
for(int s=2; s<=n; s<<=1)
{
double complex w1 = cexp(-I*2*M_PI/s);
for(int j=0; j<n; j+=s)
{
double complex wk = 1;
for(int k=j; k<j+s/2; k++)
{
double complex t = wk * x[k+s/2];
x[k+s/2] = x[k] - t;
x[k] += t;
wk *= w1;
}
}
}
}

该函数的输入参数和输出结果同递归方式实现。迭代方式实现的思路是按照蝴蝶变换的方式进行迭代计算，每一轮计算完成后，将数据重新排序，然后进行下一轮计算，直到得到最终结果。