title: FFT calculation from introduction to algorithm
body: <p>from MIT books(introduction to algorithm)  here is described Fast Fourier  transform algorithm,here is my code for implementation it</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include&lt;complex&gt;
  #include&lt;math.h&gt;
  #include&lt;vector&gt;
  #include&lt;iterator&gt;
  #include&lt;complex&gt;
  using namespace std;
  #define E 2.718
  #define PI 3.14
  #define n 8 
  void FFT(vector&lt;float&gt;&amp;a){
      vector&lt;float&gt;::iterator it;
          const double pi = std::acos(-1.0);
  const std::complex&lt;double&gt; i(0,1);
  
  complex&lt;double&gt;  wn =std::exp((2*pi*i)/8.0);
      vector&lt;float&gt;y;
      vector&lt;float&gt;y0;
      vector&lt;float&gt;y1;
  
      int omega=1;
      vector&lt;float&gt;a0;
       vector&lt;float&gt;a1;
        for (int i=0;i&lt;n-1;i+=2)
            a0[i]=a[i];
         for (int i=1;i&lt;n;i+=2)
             a1[i]=a[1];
         y0=FFT(a0);
         y1=FFT(a1);
  
          for (int k=0;k&lt;n/2-1;k++){
  
              y[0]=y0[k]+omega*y1[k];
              y[k+n/2]=y0[k]-omega*y1[k];
              omega=omega*imag(wn);
  
  
          }
          for(it=y.begin();it!=y.end();it++){
              cout&lt;&lt;*it&lt;&lt;"  ";
  
          }
  
  }
  
  int main(){
      vector&lt;int&gt;a;
      a.push_back(2);
      a.push_back(3);
      a.push_back(5);
      a.push_back(1);
      a.push_back(100);
      a.push_back(200);
      a.push_back(300);
      a.push_back(400);
      cout&lt;&lt;FFT(a)&lt;&lt;endl;
  
      return 0;
  }
  </code></pre>
  
  <p>but it shows me error list</p>
  
  <pre><code>Error   1   error C2679: binary '=' : no operator found which takes a right-hand operand of type 'void' (or there is no acceptable conversion)  c:\users\datuashvili\documents\visual studio 2010\projects\fft\fft\fft.cpp  28  1   FFT
  Error   2   error C2679: binary '=' : no operator found which takes a right-hand operand of type 'void' (or there is no acceptable conversion)  c:\users\datuashvili\documents\visual studio 2010\projects\fft\fft\fft.cpp  29  1   FFT
  Warning 3   warning C4244: '=' : conversion from 'double' to 'int', possible loss of data   c:\users\datuashvili\documents\visual studio 2010\projects\fft\fft\fft.cpp  35  1   FFT
  Error   4   error C2664: 'FFT' : cannot convert parameter 1 from 'std::vector&lt;_Ty&gt;' to 'std::vector&lt;_Ty&gt; &amp;' c:\users\datuashvili\documents\visual studio 2010\projects\fft\fft\fft.cpp  56  1   FFT
      5   IntelliSense: no operator "=" matches these operands    c:\users\datuashvili\documents\visual studio 2010\projects\fft\fft\fft.cpp  28  7   FFT
      6   IntelliSense: no operator "=" matches these operands    c:\users\datuashvili\documents\visual studio 2010\projects\fft\fft\fft.cpp  29  7   FFT
      7   IntelliSense: a reference of type "std::vector&lt;float, std::allocator&lt;float&gt;&gt; &amp;" (not const-qualified) cannot be initialized with a value of type "std::vector&lt;int, std::allocator&lt;int&gt;&gt;"    c:\users\datuashvili\documents\visual studio 2010\projects\fft\fft\fft.cpp  56  12  FFT
  </code></pre>
  
  <p>UPDATED:
  here is my  updated code</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include&lt;complex&gt;
  #include&lt;math.h&gt;
  #include&lt;vector&gt;
  #include&lt;iterator&gt;
  #include&lt;complex&gt;
  using namespace std;
  #define E 2.718
  #define PI 3.14
  #define n 8 
  vector&lt;float&gt;FFT(vector&lt;double&gt;a)
  {
      vector&lt;float&gt;::iterator it;
          const double pi = std::acos(-1.0);
  const std::complex&lt;double&gt; i(0,1);
  
  complex&lt;double&gt;  wn =std::exp((2*pi*i)/8.0);
      vector&lt;double&gt;y;
      vector&lt;double&gt;y0;
      vector&lt;double&gt;y1;
  
      double omega=1;
      vector&lt;double&gt;a0;
       vector&lt;double&gt;a1;
        for (int i=0;i&lt;n-1;i+=2)
            a0[i]=a[i];
         for (int i=1;i&lt;n;i+=2)
             a1[i]=a[1];
         FFT(a0);
         y0=a0;
         FFT(a1);
         y1=a1;
  
          for (int k=0;k&lt;n/2-1;k++){
  
              y[0]=y0[k]+omega*y1[k];
              y[k+n/2]=y0[k]-omega*y1[k];
              omega=omega*imag(wn);
  
  
          }
           return y;
  
  
  
  }
  
  int main(){
      vector&lt;double&gt;a;
      a.push_back(2);
      a.push_back(3);
      a.push_back(5);
      a.push_back(1);
      a.push_back(100);
      a.push_back(200);
      a.push_back(300);
      a.push_back(400);
  FFT(a);
  
      return 0;
  }
  </code></pre>
  
  <p>but it shows me errors yet</p>
  
  <pre><code>Error   1   error C2664: 'std::vector&lt;_Ty&gt;::vector(const std::vector&lt;_Ty&gt; &amp;)' : cannot convert parameter 1 from 'std::vector&lt;_Ty&gt;' to 'const std::vector&lt;_Ty&gt; &amp;'    c:\users\datuashvili\documents\visual studio 2010\projects\fft\fft\fft.cpp  42  1   FFT
      2   IntelliSense: no suitable user-defined conversion from "std::vector&lt;double, std::allocator&lt;double&gt;&gt;" to "std::vector&lt;float, std::allocator&lt;float&gt;&gt;" exists  c:\users\datuashvili\documents\visual studio 2010\projects\fft\fft\fft.cpp  42  11  FFT
  </code></pre>
  
  <p>please help me guys</p>