用C语言写一个FFT

FFT (快速傅里叶变换) 是一种数学算法，用于将一个复数信号从时域转换到频域。

C语言实现FFT的代码如下：

#include <math.h>

#define PI 3.14159265358979323846

void fft(double *x, double *y, int n) {
    int i, j, k, m;
    double t1, t2, u1, u2, w, p;

    j = 0;
    for (i = 0; i < n; i++) {
        if (j > i) {
            t1 = x[i];
            x[i] = x[j];
            x[j] = t1;
            t1 = y[i];
            y[i] = y[j];
            y[j] = t1;
        }
        k = n / 2;
        while (k <= j) {
            j = j - k;
            k = k / 2;
        }
        j = j + k;
    }
    m = 2;
    while (m <= n) {
        for (i = 0; i < n; i += m) {
            w = PI * 2 / m;
            for (j = i; j < i + m / 2; j++) {
                k = j + m / 2;
                t1 = x[j] - x[k];
                t2 = y[j] - y[k];
                x[j] = x[j] + x[k];
                y[j] = y[j] + y[k];
                u1 = cos(w * (j - i)) * t1 - sin(w * (j - i)) * t2;
                u2 = sin(w * (j - i)) * t1 + cos(w * (j - i)) * t2;
                x[k] = u1;
                y[k] = u2;
            }
        }
        m = m * 2;
    }
}

这是一份简单的FFT代码，它使用了基于蝴蝶算法的FFT实现。如果您不了解FFT的原理，可以先学习相关知识再阅读代码。