title: Which FFT algorithm does this code use?
body: <p>I found it online and there are no comments.</p>
  
  <p>It comes with a Complex.class that basically simulates complex numbers and their operations.</p>
  
  <p>I'd like to comment it myself but I really can't identify which algorithm is being used. I went online and found that the Cooley-Tukey algorithm is the most widespread, but I'm not sure that this code uses it.</p>
  
  <pre><code>private $dim;
  private $p;
  private $ind;
  private $func;
  private $w1;
  private $w1i;
  private $w2;
  
  public function __construct($dim) {
      $this-&gt;dim = $dim;
      $this-&gt;p = log($this-&gt;dim, 2);
  }
  
  
  public function fft($func) {
      $this-&gt;func = $func;
  
      // Copying func in w1 as a complex.
      for ($i = 0; $i &lt; $this-&gt;dim; $i++)
          $this-&gt;w1[$i] = new Complex($func[$i], 0);
  
      $w[0] = new Complex(1, 0);
      $w[1] = new Complex(cos((-2 * M_PI) / $this-&gt;dim), sin((-2 * M_PI) / $this-&gt;dim));
  
      for ($i = 2; $i &lt; $this-&gt;dim; $i++)
          $w[$i] = Complex::Cmul($w[$i-1], $w[1]);
  
      return $this-&gt;calculate($w);
  }
  
  private function calculate($w) {
      $k = 1;
      $ind[0] = 0;
  
      for ($j = 0; $j &lt; $this-&gt;p; $j++) {
          for ($i = 0; $i &lt; $k; $i++) {
              $ind[$i] *= 2;
              $ind[$i+$k] = $ind[$i] + 1;
          }
          $k *= 2;
      }
  
      for ($i = 0; $i &lt; $this-&gt;p; $i++) {
          $indw = 0;
          for ($j = 0; $j &lt; pow(2, $i); $j++) {
              $inf = ($this-&gt;dim / pow(2, $i)) * $j;
              $sup = (($this-&gt;dim / pow(2, $i)) * ($j+1)) - 1;
              $comp = ($this-&gt;dim / pow(2, $i)) / 2;
  
              for ($k = $inf; $k &lt;= floor($inf+(($sup-$inf)/2)); $k++)
                  $this-&gt;w2[$k] = Complex::Cadd(Complex::Cmul($this-&gt;w1[$k], $w[0]), Complex::Cmul($this-&gt;w1[$k+$comp], $w[$ind[$indw]]));    
  
              $indw++;
  
              for ($k = floor($inf+(($sup-$inf)/2)+1); $k &lt;= $sup; $k++)
                  $this-&gt;w2[$k] = Complex::Cadd(Complex::Cmul($this-&gt;w1[$k], $w[$ind[$indw]]), Complex::Cmul($this-&gt;w1[$k-$comp], $w[0]));
  
              $indw++;
          }
  
          for($j = 0; $j &lt; $this-&gt;dim; $j++)
              $this-&gt;w1[$j] = $this-&gt;w2[$j];
      }
  
      for ($i = 0; $i &lt; $this-&gt;dim; $i++)
          $this-&gt;w1[$i] = $this-&gt;w2[$ind[$i]];
  
      return $this-&gt;w1;
  }
  </code></pre>