fft快速傅里叶变换c语言实现

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

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

#define PI 3.14159265358979323846

void fft(int n, double complex x[n], double complex y[n])
{
    if (n == 1) {
        y[0] = x[0];
        return;
    }

    double complex xe[n / 2], xo[n / 2], ye[n / 2], yo[n / 2];

    for (int i = 0, j = 0; i < n; i += 2, j++) {
        xe[j] = x[i];
        xo[j] = x[i + 1];
    }

    fft(n / 2, xe, ye);
    fft(n / 2, xo, yo);

    for (int i = 0; i < n; i++) {
        double complex t = cexp(-I * PI * i / n) * yo[i % (n / 2)];
        y[i] = ye[i % (n / 2)] + t;
        y[(n / 2) + i] = ye[i % (n / 2)] - t;
    }
}

int main()
{
    int n = 8;
    double complex x[n], y[n];

    for (int i = 0; i < n; i++) {
        x[i] = i + 1;
    }

    fft(n, x, y);

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

    return 0;
}

以上代码中，`fft`函数实现了快速傅里叶变换的递归过程，`main`函数中的示例代码展示了如何使用`fft`函数来对长度为8的序列进行FFT变换，并输出结果。