#include <iostream>#
include #include
typedef std::complex complex;int fft(complex * x, int n, complex * y) {
int k = n >> 1; int i, j; i = j = 0; complex w(1.0, 0.0); complex wn(cos(2*M_PI/n), sin(-2*M_PI/n)); complex t(0.0, 0.0); complex * x0 = new complex[k]; complex * x1 = new complex[k]; complex * y0 = new complex[k]; complex * y1 = new complex[k]; if ((NULL == x0) || (NULL == x1) || (NULL == y0) || (NULL == y1)) { return 0; } if (1 == n) { y[0] = x[0];
return 1; }
for (i = 0; i < k ; i++) { int j = 2 * i; x0[i] = x[j]; x1[i] = x[j+1]; } if (fft(x0, k, y0) && fft(x1, k, y1)) { for (i = 0; i < k; i++) { t = y1[i] * w; y[i] = y0[i] + t; y[i+k] = y0[i] - t; w = w * wn; } } return 1;}
int main(int argc, char ** argv) { complex * td = new complex[4]; complex * fd = new complex[4]; td[0] = 1; td[1] = 2; td[2] = 3; td[3] = 4; fft(td, 4, fd); for (int i = 0; i < 4; i++) { std::cout << fd[i] << std::endl; } return 0;}