#include <iostream>
#include <vector>
#include <complex>
#include <cmath>

#define M_PI 3.14159265358979323846

typedef std::complex<double> complex_d;
typedef std::vector<complex_d> complex_array_d;

complex_array_d fft(complex_array_d& sample) {
	if (sample.size() <= 1) {
		return sample;
	}

	complex_array_d even;
	complex_array_d odd;

	bool is_even = true;
	for (auto s : sample) {
		if (is_even) {
			even.push_back(s);
		}
		else {
			odd.push_back(s);
		}
		is_even = !is_even;
	}

	complex_array_d fft_even = fft(even);
	complex_array_d fft_odd = fft(odd);
	complex_array_d result;
	result.resize(sample.size());

	for (size_t i = 0; i < sample.size() / 2; i++) {
		complex_d w = std::polar(1.0, -2 * M_PI * i / sample.size());
		result.at(i) = fft_even.at(i) + w * fft_odd.at(i);
		result.at(i + sample.size() / 2) = fft_even.at(i) - w * fft_odd.at(i);
	}
	return result;
}

int main(int argc, char** argv) {
	const int MAX_ORDER = 13;
	const bool PRINT_COEFS = true;

	for (int o = 1; o < MAX_ORDER; o++) {
		const int N = 1 << o;
		std::cout << "N: " << N << std::endl;
		complex_array_d f;
		for (int n = 0; n < N; n++) {
			f.push_back(sin(2 * M_PI * n / (double)N));
		}
		complex_array_d fft_result = fft(f);

		if (PRINT_COEFS) {
			for (auto c : fft_result) {
				std::cout << "real: " << c.real() << " im: " << c.imag() << std::endl;
			}
		}
		std::cout << std::endl;
	}

	return 0;
}