fft C语言实现

下面是一个基于C语言的FFT实现代码示例，可以参考：

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

#define PI 3.14159265358979323846

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

    double complex even[n/2], odd[n/2];

    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(-2.0*PI*i/n) * odd[i];
        x[i] = even[i] + t;
        x[i+n/2] = even[i] - t;
    }
}

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

    fft(x, n);

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

    return 0;
}

这个示例程序实现了一个递归的FFT算法，使用了C语言的复数类型 `double complex`。在 `main` 函数中，定义了一个长度为8的复数序列，然后调用 `fft` 函数进行FFT变换，并输出结果。你可以根据自己的需求改变输入序列的长度和数值。