fft算法的c语言实现

FFT算法是一种高效的数字信号处理算法，可以在O(nlogn)的时间复杂度内计算出离散傅里叶变换（DFT）。

以下是C语言实现FFT算法的代码示例（假设输入信号长度为2的n次幂）：

#include <stdio.h>
#include <math.h>

#define PI 3.14159265358979323846

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(-2.0 * PI * I * k / n) * odd[k];
        x[k] = even[k] + t;
        x[k + n/2] = even[k] - t;
    }
}

int main() {
    int n = 8; // 输入信号长度为2的n次幂
    double complex x[n];

    // 输入信号
    for (int i = 0; i < n; i++) {
        x[i] = i;
    }

    fft(x, n);

    // 输出结果
    for (int i = 0; i < n; i++) {
        printf("%f + %fi\n", creal(x[i]), cimag(x[i]));
    }

    return 0;
}

在上述代码中，使用了复数类型`double complex`，需要在程序开头引入`<complex.h>`库。

该实现中使用了递归的思想，将输入信号分成偶数和奇数部分，分别进行FFT计算，最后再合并。

需要注意的是，由于计算机浮点数计算精度的限制，实际使用时可能需要加上一些特殊处理，例如加入截断误差补偿等。