FFT的c++代码实现

下面是一个简单的FFT C代码实现：

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

#define PI 3.14159265358979323846

void fft(complex double *X, int n) {
   if (n == 1) return;
   complex double X_even[n/2], X_odd[n/2];
   for (int i = 0; i < n/2; i++) {
      X_even[i] = X[2*i];
      X_odd[i] = X[2*i + 1];
   }
   fft(X_even, n/2);
   fft(X_odd, n/2);
   for (int i = 0; i < n/2; i++) {
      complex double t = cexp(-2 * PI * I * i / n) * X_odd[i];
      X[i] = X_even[i] + t;
      X[i + n/2] = X_even[i] - t;
   }
}

int main() {
   int n = 8;
   complex double X[n];
   for (int i = 0; i < n; i++) {
      X[i] = i;
   }
   fft(X, n);
   for (int i = 0; i < n; i++) {
      printf("X[%d] = %.2f + %.2fi\n", i, creal(X[i]), cimag(X[i]));
   }
   return 0;
}

这个实现使用递归FFT算法，其实现非常简单。需要注意的是，这个实现有一个假设：输入序列长度为2的幂，如果输入序列长度不是2的幂，则需要在输入序列后面添加0以满足这个假设。