I coded up an FFT, and I'm having issues with it. I can't figure out what the problem is. It's not the 1st time I've coded the FFT, and I've compared my new FFT code (in C++) to a previous time I coded the FFT (in C#), and I don't personally see any mistakes in the way I've coded it (although the two implementations have some minor semantic differences).

Here is the graph of the signal I am sending into the function:

Attachment 9674

Here is the graph I should get as output:

Attachment 9672

And here is what I really am getting as output:

Attachment 9673

The output off the fft looks oddly like the sync function...which shouldn't be the result for a simple sine wave...

Here is my code:

Do you guys see anything wrong? The only thing that I could see is that possibly my function GetVectorRange which takes a slice of a vector from some starting index to some ending index at a stride of 2 could be functiong incorrectly...I haven't thoroughly tested that function...but is that really the problem, or do you think it could be some math mistake based off of the graph output?Code:std::vector < std::complex<double> > InternalFastFourierTransform (std::vector < std::complex<double> > input) { static std::complex<double> i = std::complex<double>(0, 1); static std::complex<double> NegativeTwoPiI = -2.0 * PI * i; int N = (int)input.size(); int halfN = N / 2; if (N == 1) { return input; } else { //Recurse and get evens/odds std::vector< std::complex<double> > evens = InternalFastFourierTransform( GetVectorRange(input, 0, N, 2) ); std::vector< std::complex<double> > odds = InternalFastFourierTransform( GetVectorRange(input, 1, N, 2) ); //Combine std::vector< std::complex<double> > result = std::vector< std::complex<double> > (N); for(int k = 0; k < halfN; k++) { std::complex<double> exponent = std::exp(NegativeTwoPiI * double(k / N)); result[k] = evens[k] + exponent * odds[k]; result[k + halfN] = evens[k] - exponent * odds[k]; } return result; } }