C语言 快速傅里叶变换

快速傅里叶变换（FFT）是一种高效的算法，用于计算离散傅里叶变换。FFT是一种分治算法，将问题分解成子问题，然后通过递归求解子问题，最终组合子问题的解来得到原问题的解。

以下是C语言中实现FFT的代码示例：

#include <math.h>

typedef struct {
    double real;
    double imag;
} complex;

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

    // 分解问题
    complex even[n/2];
    complex 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);
    fft(odd, n/2);

    // 合并子问题的解
    for (int k = 0; k < n/2; k++) {
        double theta = -2*M_PI*k/n;
        complex t = {cos(theta), sin(theta)};
        t = complex_mul(t, odd[k]);
        x[k] = complex_add(even[k], t);
        x[k+n/2] = complex_sub(even[k], t);
    }
}

complex complex_add(complex a, complex b) {
    complex c = {a.real+b.real, a.imag+b.imag};
    return c;
}

complex complex_sub(complex a, complex b) {
    complex c = {a.real-b.real, a.imag-b.imag};
    return c;
}

complex complex_mul(complex a, complex b) {
    complex c = {
        a.real*b.real - a.imag*b.imag,
        a.real*b.imag + a.imag*b.real
    };
    return c;
}

该代码使用了一个复数结构体（complex），并实现了复数的加、减、乘运算。FFT函数使用递归实现，将问题分解成子问题，并通过合并子问题的解来得到原问题的解。