Databases
StackOverflow2013
Postsdbo
POA bug in FFT Algorithm
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POA bug in FFT Algorithm
    text
    copied!<p>my friends, I am programming FFT algorithm now and I have the following program:</p> <pre><code>#include&lt;iostream&gt; #include&lt;vector&gt; #include&lt;complex&gt; #include&lt;cmath&gt; #define _USE_MATH_DEFINES #include&lt;math.h&gt; #include&lt;stdlib.h&gt; using namespace std; const complex&lt;double&gt; I(0,1); const int pi = M_PI; //This function will check if a number is a power of certain number bool checkpower(float base,float num){ float a = ceil(log(num)/log(base))-floor(log(num)/log(base)); if (a==0){ return 1; } else{ return 0; } } //Fast Fourier Transform for DFT vector&lt;complex&lt;double&gt;&gt; FFT_DFT(vector&lt;complex&lt;double&gt;&gt; samples){ int N = samples.size(); cout &lt;&lt; N &lt;&lt; endl; if(!checkpower(2,N)){ cout &lt;&lt; "Please make sure the sample size is of 2^n!" &lt;&lt; endl; exit (EXIT_FAILURE); } else{ vector&lt;complex&lt;double&gt;&gt; F(N); if(N==1){ F.push_back(samples[0]); } else{ int M = N/2; cout &lt;&lt; M &lt;&lt; endl; vector&lt;complex&lt;double&gt;&gt; O; //vector to store the odd elements vector&lt;complex&lt;double&gt;&gt; E; //vector to store the even elements //Reoder the samples for(int l=0;l&lt;M;l++){ E.push_back(samples[2*l]); O.push_back(samples[2*l+1]); } vector&lt;complex&lt;double&gt;&gt; ODFT; cout &lt;&lt; "Start recursive for odd" &lt;&lt; endl; ODFT = FFT_DFT(O); vector&lt;complex&lt;double&gt;&gt; EDFT; cout &lt;&lt; "Start recursive for even" &lt;&lt; endl; EDFT = FFT_DFT(E); for(int k=0;k&lt;M;k++){ cout &lt;&lt; real(EDFT[k]) &lt;&lt; " + "&lt;&lt; imag(EDFT[k]) &lt;&lt; "I" &lt;&lt; endl; cout &lt;&lt; real(ODFT[k]) &lt;&lt; " + "&lt;&lt; imag(ODFT[k]) &lt;&lt; "I" &lt;&lt; endl; F[k] = EDFT[k]+exp(-2.0*pi*k*I/(double)N)*ODFT[k]; F[k+M] = EDFT[k]-exp(-2.0*pi*k*I/(double)N)*ODFT[k]; cout &lt;&lt; real(F[k]) &lt;&lt; " + "&lt;&lt; imag(F[k]) &lt;&lt; "I" &lt;&lt; endl; cout &lt;&lt; real(F[k+M]) &lt;&lt; " + "&lt;&lt; imag(F[k+M]) &lt;&lt; "I" &lt;&lt; endl; } } return F; } } int main(){ vector&lt;complex&lt;double&gt;&gt; samples; samples.push_back(8.0); samples.push_back(4.0); samples.push_back(8.0); samples.push_back(0.0); vector&lt;complex&lt;double&gt;&gt; dft = FFT_DFT(samples); vector&lt;complex&lt;double&gt;&gt;::iterator item; for(item=dft.begin();item!=dft.end();item++){ cout &lt;&lt; real(*item) &lt;&lt; " + "&lt;&lt; imag(*item) &lt;&lt; "I" &lt;&lt; endl; } return 0; } </code></pre> <p>I use visual studio 2010 professional as compiler. I don't know what is wrong in my recursive algorithm, so I used the debug mode in VS and I checked the procedure line by line, but it seems it always gave me 0 for all values. And I test it with normal FFT algorithm, it works perfect. So, can anyone help me have a look on my program? I have debug this for around 4 hours and still can't find the bug. Perhaps, I did something very stupid and I didn't notice.</p> <p>(Just for your notice,in the FFT function, in order to see what really happened, I also add many cout lines)</p> <p>Thanks for helping me out!</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload