FFT returning values in wrong order

This is a discussion on FFT returning values in wrong order within the C# Programming forums, part of the General Programming Boards category; Well, you could count this as a continuation of my thread on the GD board, but now my question is ...

  1. #1
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,738

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

    "Circular logic is good because it is."

  2. #2
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    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?
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  3. #3
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,738
    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]
    Last edited by DavidP; 10-25-2007 at 11:56 AM.
    My Website

    "Circular logic is good because it is."

  4. #4
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Quote Originally Posted by DavidP View Post
    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.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. God
    By datainjector in forum A Brief History of Cprogramming.com
    Replies: 746
    Last Post: 12-22-2002, 11:01 AM
  2. cos() returning wrong result?
    By rmullen3 in forum C++ Programming
    Replies: 6
    Last Post: 08-20-2002, 11:46 PM
  3. Returning Values
    By incognito in forum C++ Programming
    Replies: 2
    Last Post: 03-17-2002, 08:31 AM
  4. Wrong order when executing?
    By R@m0n in forum C++ Programming
    Replies: 6
    Last Post: 02-10-2002, 05:04 AM
  5. What's wrong ?
    By Nutshell in forum C Programming
    Replies: 1
    Last Post: 01-13-2002, 11:00 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21