FFT returning values in wrong order

[DavidP]

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:

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??

[Sang-drax]

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?

[DavidP]

Well, using this 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:

            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]

[Sang-drax]

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.