C语言写一个DSP的FFT变换算法

以下是一个简单的C语言实现FFT（快速傅里叶变换）算法的示例代码：

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

#define PI 3.14159265358979323846

// 计算离散傅里叶变换（DFT）
void dft(double *in, double *out, int n)
{
    int i, j;
    double re, im;

    for (i = 0; i < n; i++) {
        re = 0.0;
        im = 0.0;
        for (j = 0; j < n; j++) {
            double angle = 2.0 * PI * i * j / n;
            re += in[j] * cos(angle);
            im -= in[j] * sin(angle);
        }
        out[2 * i] = re;
        out[2 * i + 1] = im;
    }
}

// 计算FFT
void fft(double *in, double *out, int n)
{
    if (n == 1) {
        out[0] = in[0];
        out[1] = 0.0;
    } else {
        int i;
        double even[n/2], odd[n/2];
        double even_fft[2*(n/2)], odd_fft[2*(n/2)];
        for (i = 0; i < n/2; i++) {
            even[i] = in[2*i];
            odd[i] = in[2*i+1];
        }
        fft(even, even_fft, n/2);
        fft(odd, odd_fft, n/2);
        for (i = 0; i < n/2; i++) {
            double angle = 2.0 * PI * i / n;
            double re = cos(angle) * odd_fft[2*i] - sin(angle) * odd_fft[2*i+1];
            double im = cos(angle) * odd_fft[2*i+1] + sin(angle) * odd_fft[2*i];
            out[2*i] = even_fft[2*i] + re;
            out[2*i+1] = even_fft[2*i+1] + im;
            out[2*i+(n/2)*2] = even_fft[2*i] - re;
            out[2*i+(n/2)*2+1] = even_fft[2*i+1] - im;
        }
    }
}

int main()
{
    double in[] = {1.0, 0.0, -1.0, 0.0};
    double out[8];
    int n = sizeof(in) / sizeof(double);
    printf("输入数据：\n");
    for (int i = 0; i < n; i++) {
        printf("%f + %fi\n", in[2*i], in[2*i+1]);
    }
    fft(in, out, n);
    printf("傅里叶变换后数据：\n");
    for (int i = 0; i < n; i++) {
        printf("%f + %fi\n", out[2*i], out[2*i+1]);
    }
    return 0;
}

该示例代码中实现了两个函数，一个是计算离散傅里叶变换（DFT）的函数dft，另一个是计算FFT的函数fft。FFT是一种优化过