fft 的c语言代码

以下是快速傅里叶变换（FFT）的C语言代码实现：

#include <stdio.h>
#include <math.h>
#define PI 3.14159265

void FFT(double complex *x, int n) {
    if (n <= 1) return;

    double complex even[n / 2];
    double complex 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 i = 0; i < n / 2; i++) {
        double complex t = cexp(-I * 2 * PI * i / n) * odd[i];
        x[i] = even[i] + t;
        x[i + n / 2] = even[i] - t;
    }
}

int main() {
    double complex x[] = {1, 2, 3, 4, 5, 6, 7, 8};
    int n = sizeof(x) / sizeof(double complex);

    FFT(x, n);

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

这里使用了C语言中的复数类型 double complex，可以通过 include <complex.h> 来引入。在FFT函数中，递归地进行分治，直到n为1时终止。然后通过递归合并的方式进行计算，最终得到FFT结果。在main函数中，我们对一个长度为8的序列进行FFT，输出结果。