Could someone be kind enough to review this Fourier transformation, please? I'm especially interested in going about unit testing the code (I don't really know where to begin, beyond applying the fft twice to retrieve the input), and have left test functions blank.
If you do spot a bug (and no doubt there are some), please don't tell me. I'd like to find them myself.
/* A simple radix 2 fast fourier transform. */ #include <complex> #include <iostream> #include <cassert> #define _USE_MATH_DEFINES #include <cmath> typedef std::complex<double> Complex; void TestSpike(Complex* data, int length){ assert( 1.0 == data[1]); } //Generates a spike in the DC bin, used for testing the fft void GenerateSpike(Complex* data, int length){ for(int i = 0 ; i < length ; i++) { if(1 == i){ data[i] = 1.0; } else { data[i] = 0.0; } } TestSpike(data, length); } void TestTwiddle(){ } void TestButterfly(){ } Complex w(int bin, int length){ return (cos(2*M_PI*bin/length), sin(2*M_PI*bin/length)); } void butterfly(Complex* data, int bin, int stepSize, int fftlength){ Complex x0 = data[bin]; Complex x1 = data[bin+stepSize]; data[bin] = x0 + w(bin, fftlength)*x1; data[bin+stepSize] = x0 - w(bin, fftlength)*x1; } //Decimation in time void FFT(Complex *data, int length){ for(int bflySize = 2 ; bflySize < length ; bflySize *= 2) { int numBflys = length/bflySize; for(int i = 0 ; i < numBflys ; i++) { int stepSize = bflySize/2; for(int j = 0 ; j < bflySize ; j+= stepSize) { butterfly(data, (bflySize*i)+j, bflySize/2, length); } } } } int Reverse(unsigned int i, int size){ int reversed = 0; while(size > 1){ reversed = (reversed >> 1) | (i & 1); i >>= 1; size >>= 1; } return reversed; } int main(int argv, char** argc){ int length; std::cout << "Please input the length of the FFT" << std::endl; std::cin >> length; std::complex<double> data[length]; GenerateSpike(data, length); FFT(data, length); for(int i = 0 ; i < length ; i++) { int j = Reverse(i,length); std::cout << data[j] << std:: endl; } return 0; } 
