title: Implementation of the Discrete Fourier Transform - FFT
body: <p>I am trying to do a project in sound processing and need to put the frequencies into another domain. Now, I have tried to implement an FFT, that didn't go well. I tried to understand the <code>z</code>-transform, that didn't go to well either. I read up and found DFT's a lot more simple to understand, especially the algorithm. So I coded the algorithm using examples but I do not know or think the output is right. (I don't have Matlab on here, and cannot find any resources to test it) and wondered if you guys knew if I was going in the right direction. Here is my code so far:</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;complex&gt;
  #include &lt;vector&gt;
  
  using namespace std;
  
  const double PI = 3.141592;
  
  vector&lt; complex&lt;double&gt; &gt; DFT(vector&lt; complex&lt;double&gt; &gt;&amp; theData)
  {
  // Define the Size of the read in vector
  const int S = theData.size();
  
  // Initalise new vector with size of S
  vector&lt; complex&lt;double&gt; &gt; out(S, 0);
  for(unsigned i=0; (i &lt; S); i++)
  {
      out[i] = complex&lt;double&gt;(0.0, 0.0);
      for(unsigned j=0; (j &lt; S); j++)
      {
          out[i] += theData[j] * polar&lt;double&gt;(1.0, - 2 * PI * i * j / S);
      }
  }
  
  return out;
  }
  
  int main(int argc, char *argv[]) {
  
  vector&lt; complex&lt;double&gt; &gt; numbers;
  
  numbers.push_back(102023);
  numbers.push_back(102023);
  numbers.push_back(102023);
  numbers.push_back(102023);
  
  vector&lt; complex&lt;double&gt; &gt; testing = DFT(numbers);
  
  for(unsigned i=0; (i &lt; testing.size()); i++)
  {
      cout &lt;&lt; testing[i] &lt;&lt; endl;
  
  }
  }
  </code></pre>
  
  <p>The inputs are:</p>
  
  <pre><code>102023               102023
  
  102023               102023
  </code></pre>
  
  <p>And the result:</p>
  
  <pre><code>(408092,       0)
  
  (-0.0666812,  -0.0666812)
  
  (1.30764e-07, -0.133362)
  
  (0.200044,    -0.200043)
  </code></pre>
  
  <p>Any help or advice would be great, I'm not expecting a lot, but, anything would be great. Thank you :)</p>