간단한 FFT 계산 함수

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

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

  // 짝수 인덱스와 홀수 인덱스로 분할합니다.
  complex double even[n / 2];
  complex double odd[n / 2];
  for (int i = 0; i < n / 2; i++) {
    even[i] = x[2 * i];
    odd[i] = x[2 * i + 1];
  }

  // 짝수 인덱스와 홀수 인덱스의 FFT를 수행합니다.
  fft(even, n / 2);
  fft(odd, n / 2);

  // FFT 결과를 결합합니다.
  for (int i = 0; i < n / 2; i++) {
    complex double w = exp(-2 * M_PI * i / n);
    x[i] = even[i] + w * odd[i];
    x[i + n / 2] = even[i] - w * odd[i];
  }
}