このコードではどのFFTアルゴリズムを使用していますか？

Question

私はそれをオンラインで見つけました。コメントはありません。

基本的に複素数とその演算をシミュレートするComplex.classが付属しています。

私は自分自身でコメントしたいと思いますが、実際にどのアルゴリズムが使用されているかはわかりません。私はオンラインに行き、Cooley-Tukeyアルゴリズムが最も普及していることを発見しましたが、私はこのコードがそれを使用しているかどうかはわかりません。

private $dim; 
private $p; 
private $ind; 
private $func; 
private $w1; 
private $w1i; 
private $w2; 

public function __construct($dim) { 
    $this->dim = $dim; 
    $this->p = log($this->dim, 2); 
} 


public function fft($func) { 
    $this->func = $func; 

    // Copying func in w1 as a complex. 
    for ($i = 0; $i < $this->dim; $i++) 
     $this->w1[$i] = new Complex($func[$i], 0); 

    $w[0] = new Complex(1, 0); 
    $w[1] = new Complex(cos((-2 * M_PI)/$this->dim), sin((-2 * M_PI)/$this->dim)); 

    for ($i = 2; $i < $this->dim; $i++) 
     $w[$i] = Complex::Cmul($w[$i-1], $w[1]); 

    return $this->calculate($w); 
} 

private function calculate($w) { 
    $k = 1; 
    $ind[0] = 0; 

    for ($j = 0; $j < $this->p; $j++) { 
     for ($i = 0; $i < $k; $i++) { 
      $ind[$i] *= 2; 
      $ind[$i+$k] = $ind[$i] + 1; 
     } 
     $k *= 2; 
    } 

    for ($i = 0; $i < $this->p; $i++) { 
     $indw = 0; 
     for ($j = 0; $j < pow(2, $i); $j++) { 
      $inf = ($this->dim/pow(2, $i)) * $j; 
      $sup = (($this->dim/pow(2, $i)) * ($j+1)) - 1; 
      $comp = ($this->dim/pow(2, $i))/2; 

      for ($k = $inf; $k <= floor($inf+(($sup-$inf)/2)); $k++) 
       $this->w2[$k] = Complex::Cadd(Complex::Cmul($this->w1[$k], $w[0]), Complex::Cmul($this->w1[$k+$comp], $w[$ind[$indw]]));  

      $indw++; 

      for ($k = floor($inf+(($sup-$inf)/2)+1); $k <= $sup; $k++) 
       $this->w2[$k] = Complex::Cadd(Complex::Cmul($this->w1[$k], $w[$ind[$indw]]), Complex::Cmul($this->w1[$k-$comp], $w[0])); 

      $indw++; 
     } 

     for($j = 0; $j < $this->dim; $j++) 
      $this->w1[$j] = $this->w2[$j]; 
    } 

    for ($i = 0; $i < $this->dim; $i++) 
     $this->w1[$i] = $this->w2[$ind[$i]]; 

    return $this->w1; 
} 

Answer 1

これはCooley-Tukeyアルゴリズムに基づく基数2のFFT実装であり、処理は「計算」関数で行われます。 FFTの長さは2の累乗でしか機能しませんが、関数自体のパラメータチェックは表示されません。

$ iは複数のFFTパス（log2（N）がNをFFTの長さとする）を繰り返し、各パスでは回転係数（$ wに格納されます）に出力が乗算されます複素和と差を求める前の前の段階から。

任意の長さのFFTを計算できる混合基数アプローチを実装する、FFTWなどのFFTの実装がはるかに優れています。