将上述fft方法改为C语言程序

以下是将上述 FFT 方法转换为 C 语言程序的示例：

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

#define PI 3.14159265358979323846

void fft(double *real, double *imag, int n) {
    int i, j, k;
    double theta, wr, wi, tempr, tempi;
    int m = (int)(log(n) / log(2));

    j = 0;
    for (i = 0; i < n; i++) {
        if (j > i) {
            tempr = real[j];
            real[j] = real[i];
            real[i] = tempr;
            tempi = imag[j];
            imag[j] = imag[i];
            imag[i] = tempi;
        }
        k = n / 2;
        while (k >= 1 && k <= j) {
            j -= k;
            k /= 2;
        }
        j += k;
    }

    for (i = 0; i < m; i++) {
        int len = pow(2, i + 1);
        theta = 2 * PI / len;
        wr = cos(theta);
        wi = sin(theta);
        for (j = 0; j < n; j += len) {
            double w_real = 1;
            double w_imag = 0;
            for (k = 0; k < len / 2; k++) {
                tempr = w_real * real[j + k + len / 2] - w_imag * imag[j + k + len / 2];
                tempi = w_real * imag[j + k + len / 2] + w_imag * real[j + k + len / 2];
                real[j + k + len / 2] = real[j + k] - tempr;
                imag[j + k + len / 2] = imag[j + k] - tempi;
                real[j + k] += tempr;
                imag[j + k] += tempi;
                tempr = w_real * wr - w_imag * wi;
                tempi = w_real * wi + w_imag * wr;
                w_real = tempr;
                w_imag = tempi;
            }
        }
    }
}

int main() {
    int n = 8;
    double real[] = {1, 2, 3, 4, 5, 6, 7, 8};
    double imag[] = {0, 0, 0, 0, 0, 0, 0, 0};
    fft(real, imag, n);
    for (int i = 0; i < n; i++) {
        printf("%f + %fi\n", real[i], imag[i]);
    }
    return 0;
}

此代码采用了递归方法，以一种更易于理解的方式实现了FFT算法。在此示例中，我们将其用于一个长度为8的实数组，但它可以轻松地扩展到更大的数据集。