用C语言写一个fft算法

好的，以下是一个简单的C语言实现FFT算法的代码：

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

#define PI 3.14159265358979323846

void fft(double *x, double *y, int n)
{
    if (n == 1) return;

    double xr[n/2], xi[n/2], yr[n/2], yi[n/2];
    for (int i = 0; i < n/2; i++) {
        xr[i] = x[2*i];
        xi[i] = x[2*i+1];
        yr[i] = y[2*i];
        yi[i] = y[2*i+1];
    }

    fft(xr, xi, n/2);
    fft(yr, yi, n/2);

    for (int i = 0; i < n/2; i++) {
        double t = xr[i], u = xi[i];
        double v = yr[i], w = yi[i];
        double angle = -2 * PI * i / n;
        double cosA = cos(angle), sinA = sin(angle);
        x[i] = t + cosA * v - sinA * w;
        y[i] = u + cosA * w + sinA * v;
        x[i+n/2] = t - cosA * v + sinA * w;
        y[i+n/2] = u - cosA * w - sinA * v;
    }
}

int main()
{
    int n = 8;
    double x[] = {1, 0, 1, 0, 1, 0, 1, 0};
    double y[] = {0, 0, 0, 0, 0, 0, 0, 0};

    fft(x, y, n);

    printf("FFT result:\n");
    for (int i = 0; i < n; i++) {
        printf("%f + %fi\n", x[i], y[i]);
    }

    return 0;
}

这个代码实现了一个简单的FFT算法，可以对长度为2的幂次的复数序列进行FFT变换。