FFT returning values in wrong order
Well, you could count this as a continuation of my thread on the GD board, but now my question is MUCH more C# specific, and therefore I decided to go ahead and post it here.
I am nearly done with the program now...I only have one bug remaining.
When I do the FFT of an array of values, I get all the correct values returned to me, but in the wrong order.
They should be returned in the order:
1 2 3 4
I get them back in the order:
1 4 3 2
Here is my FFT code:
How can I change the code to get the result in the right order??
static ArrayList FFT(ArrayList a)
//Check the length of the list that has been passed to us
int n = a.Count;
if (n == 1)
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);
Complex omega = new Complex(1, 0);
//Create even/odd lists
ArrayList even = new ArrayList(0);
ArrayList odd = new ArrayList(0);
for (int i = 0; i < a.Count; i++)
if (i % 2 == 0)
ArrayList Aeven = FFT(even);
ArrayList Aodd = FFT(odd);
ArrayList Areturn = new ArrayList(n);
for (int k = 0; k < n; k++)
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;