Well, using this code:

Code:

for ( int k = 0; k <= ((n / 2) - 1); k++ )
{
Areturn[k] = (Complex)Aeven[k] + omega * (Complex)Aodd[k];
Areturn[k + (n / 2)] = (Complex)Aeven[k] - omega * (Complex)Aodd[k];
omega = omega * omega_n;
}

I tried changing the + and - signs around, and I also tried flipping the "evens" and "odds" with each other...but to no avail.

One of my friends just told me that I might be calculating omega incorrectly:

Code:

Complex myE = new Complex ( Math.E, 0 );
Complex exponent = new Complex ( 2.0 * Math.PI / (double)n );
Complex omega_n = Complex.Pow(myE, exponent * Complex.I);

So my omega that I am calculating is: w = e^(2 * pi * i / n)

My friend said it should be: w = e^(-2 * pi * i / n)

Unfortunately I am currently on a public computer without access to my code and without access to a C# compiler...so I can't really test it to see if it would work...although I could do a couple tests by hand really quick.

Does that seem like it could be the bug to you?

[edit]

After a quick test by hand it seems that by making that change, it fixed the bug.

It kind of confuses me though because every text my teacher has given me has said that w = e^(2 * pi * i / n), and not e^(-2 * pi * i / n)

[/edit]