円周率.jp > 多数桁計算 > FFT > 実装方式

実装方式

FFTには大きく分けて2種類の実装方法がある. 一方は日本語の本・サイトでも多く取り扱われている in-place 型 FFT で,もう一方は self-sorting 型 FFT である. 大雑把なメリット・デメリットとしては,前者は入力データの領域だけを用いて計算できるが,そのために処理の最初,もしくは最後にデータの並び替えが必要になる. 一方後者はデータの配置換えが必要ない代わりに,入出力サイズと同じサイズの計算領域が必要となる.

プログラムを実装する際にどちらの方式の方が良いかは細かな実装やユーザ次第となるので決定的な言及はできないが, 大まかには小メモリ動作を目指すなら前者を,速さを求めるなら後者を使用する印象である.

Cooley-Tukey 型 in-place FFT

FFT(x[], n) {
    bitrev(x[], n);
    for( m = 1 ; m < n ; m = m * 2 ) {
        for( j = 0 ; j < m ; j++ ) {
            w = exp(-i * π * j / m)
            for( k = j ; k < n ; k = k + 2 * m ) {
                X0 = x[k], X1 = w * x[k+m];
                x[k  ] = X0 + X1;
                x[k+m] = X0 - X1;
            }
        }
    }
}

Stockham 型 self-sorting FFT

FFT(x[], n) {
    for( H = 1 ; H < n ; H = H * 2 ) {
        W = n / H / 2;
        y[] = x[];  // x[] から y[] に全データコピー
        for( k = 0 ; k < H ; k++ ) {
            w = exp(-i * π * k / H);
            for( j = 0 ; j < W ; j++ ) {
                Y0 = y[2*W*k+j]; Y1 = y[2*W*k+j+W] * w;
                x[W* k   +j] = Y0 + Y1;
                x[W*(k+H)+j] = Y0 - Y1;
            }
        }
    }
}

FFT の高速演算を行うために様々な方法が提案されており, それらの殆どは上記の実装方法がどちらの方式であっても適用することができる. in-place 型 FFT については[JW06]が詳しいので,本サイトでは self-sorting 型 FFT を用いて説明する.