用C语言写一个快速傅里叶变换算法

好的，下面是一个使用C语言实现快速傅里叶变换（FFT）算法的示例代码：

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

#define PI 3.141592653589793238462643383279502884197169399375105820974944592307816406286

// 计算复数加法
void complex_add(double *a, double *b, double *c) {
    c[0] = a[0] + b[0];
    c[1] = a[1] + b[1];
}

// 计算复数减法
void complex_sub(double *a, double *b, double *c) {
    c[0] = a[0] - b[0];
    c[1] = a[1] - b[1];
}

// 计算复数乘法
void complex_mul(double *a, double *b, double *c) {
    c[0] = a[0] * b[0] - a[1] * b[1];
    c[1] = a[0] * b[1] + a[1] * b[0];
}

// 快速傅里叶变换
void fft(double *x, double *y, int n, int sign) {
    if (n == 1) {
        return;
    }

    double a[2], b[2], c[2];
    double wn[2] = {cos(2 * PI / n), sign * sin(2 * PI / n)};
    double w[2] = {1, 0};
    int i, j, k;

    fft(x, y, n / 2, sign);
    fft(x + n / 2, y + n / 2, n / 2, sign);

    for (i = 0; i < n / 2; i++) {
        j = i + n / 2;
        complex_mul(x + j, w, a);
        complex_add(x + i, a, b);
        complex_sub(x + i, a, c);
        x[i] = b[0];
        x[j] = c[0];
        y[i] = b[1];
        y[j] = c[1];
        complex_mul(w, wn, w);
    }
}

int main() {
    int n = 8;
    int i;

    double x[] = {1, 2, 3, 4, 0, 0, 0, 0};
    double y[] = {0, 0, 0, 0, 0, 0, 0, 0};

    fft(x, y, n, 1);

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

    return 0;
}

这个示例代码实现了一个简单的FFT算法，它可以计算一个长度为8的实数序列的傅里叶变换。在实际使用中，需要根据具体的需求对算法进行优化和扩展。