写一个fft的c++版本

以下是一个简单的 FFT C 代码示例：

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

#define PI 3.14159265358979323846

typedef struct {
double real;
double imag;
} complex;

void fft(complex *x, int n) {
int i, j, k;
complex t, w;
double theta;
int m = log(n) / log(2);

for (i = 0; i < n; i++) {
j = 0;
for (k = 0; k < m; k++) {
j <<= 1;
j |= (i >> k) & 1;
}
if (j < i) {
t = x[i];
x[i] = x[j];
x[j] = t;
}
}

for (i = 1; i <= m; i++) {
int le = pow(2, i - 1);
int le2 = le / 2;
w.real = 1.0;
w.imag = 0.0;
theta = 2.0 * PI / (double)le;
complex wn;
wn.real = cos(theta);
wn.imag = -sin(theta);
for (j = 0; j < le2; j++) {
for (k = j; k < n; k += le) {
int kt = k + le2;
t.real = w.real * x[kt].real - w.imag * x[kt].imag;
t.imag = w.real * x[kt].imag + w.imag * x[kt].real;
x[kt].real = x[k].real - t.real;
x[kt].imag = x[k].imag - t.imag;
x[k].real += t.real;
x[k].imag += t.imag;
}
w.real = w.real * wn.real - w.imag * wn.imag;
w.imag = w.real * wn.imag + w.imag * wn.real;
}
}
}

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

fft(x, n);

for (i = 0; i < n; i++) {
printf("%f + %fi\n", x[i].real, x[i].imag);
}

return 0;
}