写一个FFT的C语言函数

### 回答1：

下面是一个用 C 语言编写的快速傅立叶变换（FFT）函数：void fft(int dir,long m,double *x,double *y)
{
long n,i,i1,j,k,i2,l,l1,l2;
double c1,c2,tx,ty,t1,t2,u1,u2,z; /* Calculate the number of points */
n = 1;
for (i=0;i<m;i++)
n *= 2; /* Do the bit reversal */
i2 = n >> 1;
j = 0;
for (i=0;i<n-1;i++) {
if (i < j) {
tx = x[i];
ty = y[i];
x[i] = x[j];
y[i] = y[j];
x[j] = tx;
y[j] = ty;
}
k = i2;
while (k <= j) {
j -= k;
k >>= 1;
}
j += k;
} /* Compute the FFT */
c1 = -1.0;
c2 = 0.0;
l2 = 1;
for (l=0;l<m;l++) {
l1 = l2;
l2 <<= 1;
u1 = 1.0;
u2 = 0.0;
for (j=0;j<l1;j++) {
for (i=j;i<n;i+=l2) {
i1 = i + l1;
t1 = u1 * x[i1] - u2 * y[i1];
t2 = u1 * y[i1] + u2 * x[i1];
x[i1] = x[i] - t1;
y[i1] = y[i] - t2;
x[i] += t1;
y[i] += t2;
}
z = u1 * c1 - u2 * c2;
u2 = u1 * c2 + u2 * c1;
u1 = z;
}
c2 = sqrt((1.0 - c1) / 2.0);
if (dir == 1)
c2 = -c2;
c1 = sqrt((1.0 + c1) / 2.0);
} /* Scaling for forward transform */
if (dir == 1) {
for (i=0;i<n;i++) {
x[i] /= n;
y[i] /= n;
}
}
}

### 回答2：
以下是一个用C语言编写的FFT（快速傅里叶变换）函数的示例：

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

#define PI 3.14159265

void fft(complex double x[], int size) {
    if (size <= 1) {
        return;
    }
    
    complex double even[size / 2];
    complex double odd[size / 2];
    
    for (int i = 0; i < size / 2; i++) {
        even[i] = x[2 * i];
        odd[i] = x[2 * i + 1];
    }
    
    fft(even, size / 2);
    fft(odd, size / 2);
    
    for (int k = 0; k < size / 2; k++) {
        complex double t = cexp(-I * 2 * PI * k / size) * odd[k];
        x[k] = even[k] + t;
        x[k + size / 2] = even[k] - t;
    }
}

int main() {
    // 示例使用的输入数据
    int size = 8;
    complex double x[] = {1, 2, 3, 4, 5, 6, 7, 8};
    
    // 对输入数据进行快速傅里叶变换
    fft(x, size);
    
    // 输出结果
    printf("FFT结果：");
    for (int i = 0; i < size; i++) {
        printf("%.2f + %.2fi, ", creal(x[i]), cimag(x[i]));
    }
    
    return 0;
}

这个FFT函数使用递归的方式实现傅里叶变换，并且根据蝶形算法的原理进行计算。函数的输入参数为一个复数数组x和数组的大小size。函数将输入数组进行原地傅里叶变换，并将结果保存在同一数组x中。在示例代码中，输入的大小为8，并且输入数据为{1, 2, 3, 4, 5, 6, 7, 8}。最后，通过打印结果，可以看到变换后的结果。请注意，这个示例代码只是FFT的一个简单实现，实际的FFT算法可能会有更多的优化和复杂性。