title: Simple in-place discrete fourier transform ( DFT )
body: <p>I'm writing a very simple in-place DFT.  I am using the formula shown here:
  <a href="http://en.wikipedia.org/wiki/Discrete_Fourier_transform#Definition" rel="noreferrer">http://en.wikipedia.org/wiki/Discrete_Fourier_transform#Definition</a> along with Euler's formula to avoid having to use a complex number class just for this.  So far I have this:</p>
  
  <pre><code>private void fft(double[] data)
          {
              double[] real = new double[256];
              double[] imag = new double[256];
              double pi_div_128 = -1 * Math.PI / 128;
              for (int k = 0; k &lt; 256; k++)
              {
                  for (int n = 0; n &lt; 256; n++)
                  {
                      real[k] += data[k] * Math.Cos(pi_div_128 * k * n);
                      imag[k] += data[k] * Math.Sin(pi_div_128 * k * n);
                  }
                  data[k] = Math.Sqrt(real[k] * real[k] + imag[k] * imag[k]);
              }
          }
  </code></pre>
  
  <p>But the Math.Cos and Math.Sin terms eventually go both positive and negative, so as I'm adding those terms multiplied with data[k], they cancel out and I just get some obscenely small value.  I see how it is happening, but I can't make sense of how my code is perhaps mis-representing the mathematics.  Any help is appreciated.  FYI, I do have to write my own, I realize I can get off-the shelf FFT's.</p>