title: Cooley-Tukey FFT in R radix-2 DIT case
body: <p>So I've been trying to (manually) implement the Cooley-Turkey FFT algorithm in R (for Inputs with size N=n^2). I tried:</p>
  
  <pre><code>myfft &lt;- function(s){
    N &lt;- length(s)
    if (N != 1){
      s[1:(N/2)] &lt;- myfft(s[(1:(N/2))*2-1])
      s[(N/2+1):N] &lt;- myfft(s[(1:(N/2))*2])
  
      for (k in 1:(N/2)){
        t &lt;- s[k]
        s[k] &lt;- t + exp(-1i*2*pi*(k-1)/N) * s[k+N/2]
        s[k+N/2] &lt;- t - exp(-1i*2*pi*(k-1)/N) * s[k+N/2]
      }
    }
    s
  }
  </code></pre>
  
  <p>This compiles, but for n>1, N=2^n it does not compute the right values. I implemented a DFT-function and used the fft() function to compare, both compute, when normalized, give the same values, but seem to disagree with my algorithm above.</p>
  
  <p>If anyone feels interested and sees where I went wrong, help would be greatly appreciated, I'm going mad searching for the mistake and am starting to question, if I even ever understood this FFT algorithm.</p>
  
  <p>UPDATE: I fixed it, I'm not 100% sure where the problem exactly was, but here is the working implementation:</p>
  
  <pre><code>myfft &lt;- function(s){
    N &lt;- length(s)
    if (N != 1){
      t &lt;- s
      t[1:(N/2)] &lt;- myfft(s[(1:(N/2))*2-1]) # 1 3 5 7 ... 
      t[(N/2+1):N] &lt;- myfft(s[(1:(N/2))*2]) # 2 4 6 8 ... 
  
      s[1:(N/2)] &lt;- t[1:(N/2)] + exp(-1i*2*pi*(0:(N/2-1))/N) * t[(N/2+1):N]
      s[(N/2+1):N] &lt;- t[1:(N/2)] - exp(-1i*2*pi*(0:(N/2-1))/N) * t[(N/2+1):N]
  
    }
    return(s)
  }
  </code></pre>