|
10-24-2007, 11:35 PM
| #1 |
| l'Anziano  Join Date: Aug 2001
Posts: 2,630
| FFT returning values in wrong order 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;
}
|
| DavidP is offline |  |
|
10-25-2007, 07:46 AM
| #2 | |
| and the hat of marbles  Join Date: May 2002 Location: Lund, Sweden
Posts: 2,041
| Quote:
__________________ Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling | |
| Sang-drax is offline | |
|
10-25-2007, 11:43 AM
| #3 |
| l'Anziano Join Date: Aug 2001
Posts: 2,630
| 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;
}
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);
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. |
| DavidP is offline | |
|
10-25-2007, 01:15 PM
| #4 | |
| and the hat of marbles Join Date: May 2002 Location: Lund, Sweden
Posts: 2,041
| Quote:
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 | |
| Sang-drax is offline | |
 |
| Thread Tools | |
| Display Modes | |
|
Similar Threads | ||||
| Thread | Thread Starter | Forum | Replies | Last Post |
| God | datainjector | A Brief History of Cprogramming.com | 746 | 12-22-2002 12:01 PM |
| cos() returning wrong result? | rmullen3 | C++ Programming | 6 | 08-20-2002 11:46 PM |
| Returning Values | incognito | C++ Programming | 2 | 03-17-2002 09:31 AM |
| Wrong order when executing? | R@m0n | C++ Programming | 6 | 02-10-2002 06:04 AM |
| What's wrong ? | Nutshell | C Programming | 1 | 01-14-2002 12:00 AM |
Linear Mode
