快速傅里叶变换用C代码实现

快速傅里叶变换(FFT)是一种高效的算法，用于计算离散傅里叶变换(DFT)。以下是一个用C语言实现FFT的示例代码：

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

#define PI 3.14159265358979323846

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

    double complex *even = malloc(n/2 * sizeof(double complex));
    double complex *odd = malloc(n/2 * sizeof(double complex));

    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 i = 0; i < n/2; i++) {
        double complex t = cexp(-I * 2 * PI * i / n) * odd[i];
        x[i] = even[i] + t;
        x[i+n/2] = even[i] - t;
    }

    free(even);
    free(odd);
}

int main()
{
    int n = 8;
    double complex x[] = {1, 0, 2, 0, 3, 0, 4, 0};

    fft(x, n);

    for (int i = 0; i < n; i++)
        printf("%f + %fi\n", creal(x[i]), cimag(x[i]));

    return 0;
}

这个代码实现了一个基于递归的FFT算法，用于计算长度为2的幂次的DFT。它使用了复数类型和复数运算，以及递归函数调用。