用C语言写基于蝶形算法FFT

好的，以下是基于蝶形算法的FFT的C语言代码：

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

#define PI 3.14159265358979323846

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

// 计算复数的乘积
complex complex_multiply(complex a, complex b) {
    complex c;
    c.real = a.real * b.real - a.imag * b.imag;
    c.imag = a.real * b.imag + a.imag * b.real;
    return c;
}

// 计算复数的加法
complex complex_add(complex a, complex b) {
    complex c;
    c.real = a.real + b.real;
    c.imag = a.imag + b.imag;
    return c;
}

// 计算复数的减法
complex complex_subtract(complex a, complex b) {
    complex c;
    c.real = a.real - b.real;
    c.imag = a.imag - b.imag;
    return c;
}

// 蝶形运算
void butterfly(complex *a, int n) {
    int i, j, k;
    complex t, w;
    for (i = 0, j = 1; j < n - 1; j++) {
        for (k = n >> 1; k > (i ^= k); k >>= 1);
        if (j < i) {
            t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }
    for (i = 2; i <= n; i <<= 1) {
        for (j = 0; j < n; j += i) {
            for (k = 0, w.real = 1, w.imag = 0; k < i / 2; k++) {
                t = complex_multiply(w, a[j + k + i / 2]);
                a[j + k + i / 2] = complex_subtract(a[j + k], t);
                a[j + k] = complex_add(a[j + k], t);
                w = complex_multiply(w, (complex) { cos(2 * k * PI / i), -sin(2 * k * PI / i)});
            }
        }
    }
}

// FFT计算
void fft(complex *a, int n) {
    butterfly(a, n);
}

int main() {
    // 测试
    int n = 8;
    complex a[] = {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}, {6, 0}, {7, 0}, {8, 0}};
    fft(a, n);
    for (int i = 0; i < n; i++) {
        printf("%.2lf + %.2lfi\n", a[i].real, a[i].imag);
    }
    return 0;
}

这里实现了一个基于蝶形算法的FFT，其中复数运算使用了结构体`complex`来表示，同时实现了复数加法、减法和乘法的函数。在`butterfly`函数中实现了蝶形运算，而在`fft`函数中使用了蝶形运算来计算FFT。在`main`函数中进行了简单的测试。