c语言fft

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

#define PI 3.14159265358979323846

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

    complex double even[n / 2], 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, inverse);
    fft(odd, n / 2, inverse);

    for (int k = 0; k < n / 2; ++k) {
        complex double t = cexp(I * PI * k * (inverse ? -2 : 2) / n) * odd[k];
        x[k] = even[k] + t;
        x[k + n / 2] = even[k] - t;
    }
}

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

    fft(x, n, 0); // 正向FFT

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

    fft(x, n, 1); // 逆向FFT

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

    return 0;
}