# FFT returning values in wrong order

• 10-24-2007
DavidP
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:

Code:

```static ArrayList FFT(ArrayList a)         {             //Check the length of the list that has been passed to us             int n = a.Count;             if (n == 1)                 return a;             //Create omega             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)                     even.Add(a[i]);                 else odd.Add(a[i]);             }             //Recurse             ArrayList Aeven = FFT(even);             ArrayList Aodd = FFT(odd);             //Combine lists             ArrayList Areturn = new ArrayList(n);             for (int k = 0; k < n; k++)                 Areturn.Insert(k, Complex.Zero);                         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;             }             //Return             return Areturn;         }```
How can I change the code to get the result in the right order??
• 10-25-2007
Sang-drax
Quote:

1 2 3 4

I get them back in the order:

1 4 3 2
Place 4 and place 2 should be conjugates of each other. Maybe a sign somewhere?
• 10-25-2007
DavidP
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?

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]
• 10-25-2007
Sang-drax
Quote:

Originally Posted by DavidP
Does that seem like it could be the bug to you?

Yes! That's it!

There's really no right and wrong here... both work as long as you're consistent in FFT and IFFT, so your teacher is also right.