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

快速傅里叶变换（FFT）是一种快速计算离散傅里叶变换（DFT）的算法。下面是用C语言实现FFT算法的代码：

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

#define PI 3.141592653589793

void fft(double *real, double *imag, int n)
{
    int i, j, k, m;
    double c, s, tr, ti;

    j = 0;
    for (i = 0; i < n - 1; i++) {
        if (i < j) {
            tr = real[j];
            ti = imag[j];
            real[j] = real[i];
            imag[j] = imag[i];
            real[i] = tr;
            imag[i] = ti;
        }
        k = n / 2;
        while (k <= j) {
            j -= k;
            k /= 2;
        }
        j += k;
    }

    for (m = 2; m <= n; m *= 2) {
        for (i = 0; i < n; i += m) {
            for (j = i; j < i + m / 2; j++) {
                k = j + m / 2;
                c = cos(2 * PI * (j - i) / m);
                s = sin(2 * PI * (j - i) / m);
                tr = real[k] * c - imag[k] * s;
                ti = real[k] * s + imag[k] * c;
                real[k] = real[j] - tr;
                imag[k] = imag[j] - ti;
                real[j] += tr;
                imag[j] += ti;
            }
        }
    }
}

void print_array(double *arr, int n)
{
    int i;
    for (i = 0; i < n; i++) {
        printf("%f ", arr[i]);
    }
    printf("\n");
}

int main()
{
    double real[] = {1, 2, 3, 4, 5, 6, 7, 8};
    double imag[] = {0, 0, 0, 0, 0, 0, 0, 0};
    int n = sizeof(real) / sizeof(real[0]);

    printf("Original data:\n");
    print_array(real, n);

    fft(real, imag, n);

    printf("FFT result:\n");
    print_array(real, n);
    print_array(imag, n);

    return 0;
}

上面的代码实现了一个简单的FFT算法，可以用来计算长度为2的幂次的复数序列的DFT。在这个实现中，我们使用了递归分治的思想，将序列分为两半，并对每一半进行递归计算。在计算过程中，我们使用了旋转因子来实现复数乘法。最终，我们得到了实部和虚部两个数组，它们分别表示了原始序列的DFT的实部和虚部。

在使用这个代码时，你需要将你的数据存储在一个双精度浮点数数组中，然后将这个数组作为参数传递给fft()函数。这个函数会将实部和虚部两个数组作为输出参数，计算出DFT的实部和虚部，并存储在这两个数组中。