title: C: Numerical Recipies (FFT)
body: <p>This question is directed at any fans of Numerical Recipes or anyone that understands FFT well.</p>
  
  <p>Can anyone explain why the real component is calculated by -2*(sin(theta/2))^2 ?
  I can't seem to wrap my head around it. I've seen other examples such as <a href="http://www.dspdimension.com/admin/dft-a-pied/" rel="nofollow noreferrer">http://www.dspdimension.com/admin/dft-a-pied/</a> tutorial which simply takes cos(theta) as real and -sin(theta) as imaginary. I've also seen here in basic <a href="http://www.dspguide.com/ch12/3.htm" rel="nofollow noreferrer">http://www.dspguide.com/ch12/3.htm</a> which lists it as cos(theta) as real and -sin(theta) as imaginary. I can think of a few more resources that simply take the cos and -sin as real and imaginary.</p>
  
  <pre><code>cos(theta) = 1-2*(sin(theta/2))^2
  </code></pre>
  
  <p>if the above trig identity is true, then why does this not folllow?</p>
  
  <pre><code>theta=isign*(6.28318530717959/mmax);
  wtemp=sin(0.5*theta);
  wpr = -2.0*wtemp*wtemp;
  wpi=sin(theta);
  </code></pre>
  
  <p>I am assuming Numerical Recipe must be using some trig identity? I can't seem to figure it out and the book doesn't explain at all.</p>
  
  <p>Code found here: <a href="http://ronispc.chem.mcgill.ca/ronis/chem593/sinfft.c.html" rel="nofollow noreferrer">http://ronispc.chem.mcgill.ca/ronis/chem593/sinfft.c.html</a></p>
  
  <pre><code>#define SWAP(a,b) tempr=(a);(a)=(b);(b)=tempr
  
  void four1(double *data,unsigned long nn,int isign)
  {
          unsigned long n,mmax,m,j,istep,i;
          double wtemp,wr,wpr,wpi,wi,theta;
          double tempr,tempi;
  
          n=nn &lt;&lt; 1;
          j=1;
          for (i=1;i&lt;n;i+=2) {
                  if (j &gt; i) {
                          SWAP(data[j],data[i]);
                          SWAP(data[j+1],data[i+1]);
                  }
                  m=n &gt;&gt; 1;
                  while (m &gt;= 2 &amp;&amp; j &gt; m) {
                          j -= m;
                          m &gt;&gt;= 1;
                  }
                  j += m;
          }
          mmax=2;
          while (n &gt; mmax) {
                  istep=mmax &lt;&lt; 1;
                  theta=isign*(6.28318530717959/mmax);
                  wtemp=sin(0.5*theta);
                  wpr = -2.0*wtemp*wtemp;
                  wpi=sin(theta);
                  wr=1.0;
                  wi=0.0;
                  for (m=1;m&lt;mmax;m+=2) {
                          for (i=m;i&lt;=n;i+=istep) {
                                  j=i+mmax;
                                  tempr=wr*data[j]-wi*data[j+1];
                                  tempi=wr*data[j+1]+wi*data[j];
                                  data[j]=data[i]-tempr;
                                  data[j+1]=data[i+1]-tempi;
                                  data[i] += tempr;
                                  data[i+1] += tempi;
                          }
                          wr=(wtemp=wr)*wpr-wi*wpi+wr;
                          wi=wi*wpr+wtemp*wpi+wi;
                  }
                  mmax=istep;
          }
  }
  #undef SWAP
  </code></pre>