Fourier transformation

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 
#include 
#include 
#define _USE_MATH_DEFINES
#include 

typedef std::complex 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  1){
    reversed = (reversed >> 1) | (i & 1);
    i >>= 1;
    size >>= 1;
  }
  return reversed;
}

int main(int argv, char** argc){

  int length;
  std::cout > length;
  std::complex 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;
}

Using operator== on doubles isn't usually a good idea, although it may be okay in the TestSpike case as you know you've assigned exactly 1.0 to it previously.

I would write GenerateSpike as follows:

void GenerateSpike(Complex* data, int length) {
  std::fill(data, data+length, 0.0);
  if (length >= 2)
    data[1] = 1.0;
}

By the way, you're not checking that the array is of sufficient length in TestSpike.

stepSize in FFT does not depend on the parameters of the second-outermost loop, so it should be in the outermost loop. You should also use stepSize instead of bflySize/2 in the call to butterfly.

About testing: w, butterfly, Reverse, and FFT all seem to be pure functions, so you can test them simply by checking the return value. You might want to get a framework like GTest or Boost.Test to make them easier to write.

StackExchange Code Review Q#9651, answer score: 2