Spaghetti Source logo

高速フーリエ変換

目的

高速フーリエ変換は長さ n の複素数列 { a[k] } に対し,A[m] = Σa[k] ω[mk] で定義される複素数列 { A[m] } を高速に求めるアルゴリズムである.詳しくは大浦先生の解説を参照 (http://momonga.t.u-tokyo.ac.jp/~ooura/fftman/index.html).

計算量

O(n log n).

使い方

int n
配列の長さ.2 のべきでなければならない.
double theta
回転角.順変換のとき 2*PI/n を指定し,逆変換のとき -2*PI/n を指定する.
Complex a[]
変換する配列.結果は in place で変換される.逆変換の場合は結果をさらに 1/n 倍する必要がある.

ソースコード

const double PI = 4.0*atan(1.0);

typedef complex<double> Complex;
const Complex I(0, 1);

void fft(int n, double theta, Complex a[]) {
  for (int m = n; m >= 2; m >>= 1) {
    int mh = m >> 1;
    for (int i = 0; i < mh; i++) {
      Complex w = exp(i*theta*I);
      for (int j = i; j < n; j += m) {
        int k = j + mh;
        Complex x = a[j] - a[k];
        a[j] += a[k];
        a[k] = w * x;
      }
    }
    theta *= 2;
  }
  int i = 0;
  for (int j = 1; j < n - 1; j++) {
    for (int k = n >> 1; k > (i ^= k); k >>= 1);
    if (j < i) swap(a[i], a[j]);
  }
}

Verified

前原 貴憲(maehara@prefield.com).

Last Modified: 2006.12.11 08:51:44.