Basic implementation of Cooley-Tukey FFT algorithm in C++

FFT.c

#include "FFT.h"

void fft(int *x_in, 
	std::complex<double> *x_out,
	int N) {

	// Make copy of array and apply window
	for (int i = 0; i < N; i++) {
		x_out[i] = std::complex<double>(x_in[i], 0);
		x_out[i] *= 1; // Window
	}

	// Start recursion
	fft_rec(x_out, N);
}

void fft_rec(std::complex<double> *x, int N) {
	// Check if it is splitted enough
	if (N <= 1) {
		return;
	}

	// Split even and odd
	std::complex<double> odd[N/2];
	std::complex<double> even[N/2];
	for (int i = 0; i < N / 2; i++) {
		even[i] = x[i*2];
		odd[i] = x[i*2+1];
	}

	// Split on tasks
	fft_rec(even, N/2);
	fft_rec(odd, N/2);


	// Calculate DFT
	for (int k = 0; k < N / 2; k++) {
		std::complex<double> t = exp(std::complex<double>(0, -2 * M_PI * k / N)) * odd[k];
		x[k] = even[k] + t;
		x[N / 2 + k] = even[k] - t;
	}
}

FFT.h

/* ---------------------------------------------------------------------------
** Basic implementation of Cooley-Tukey FFT algorithm in C++ 
**
** Author: Darko Lukic <[email protected]>
** -------------------------------------------------------------------------*/

#ifndef FFT_h
#define FFT_h

#include <cmath>
#include <complex>

extern void fft(int *x_in, 
	std::complex<double> *x_out,
	int N);
void fft_rec(std::complex<double> *x, int N);

#endif

This is a great implementation. No weird data types and building stuff with cmake, just basic, working code.

This is pretty good, but is it actually Cooley-Tukey FFT algorithm? I am looking for a non-recursive FFT algotithm...

It won't give you proper results in case if you want to do some signal processing with it, since, for example, fft of [1, 2, 3] and same signal padded with zero to nearest power of 2 give you completely different results. So i still wondering how to deal with it.