【競プロer向け】FFT を習得しよう！

こんにちは、20B の @tatyam です。この記事は、traP夏のブログリレー 33日目の記事です。

高速フーリエ変換 といえば、競技プログラミングで数列の畳み込みなどに使われるテクニックですね。
今日は高速フーリエ変換と高速フーリエ変換を利用した畳み込みを習得していきましょう。

ポエム

一般的なフーリエ変換の定義 / 説明と異なる部分があるかもしれませんが、競プロであればこれで十分だと思います。
AtCoder では AC Library さえ使えれば FFT は理解しなくて良いことになっていますね。
まあでも、中身を理解するといろいろと応用ができるようになるので、理解する価値はかなり高いでしょう。

離散フーリエ変換 (DFT)

離散フーリエ変換 とは、高速フーリエ変換の元になっているものです。離散フーリエ変換の特殊な場合を高速化したものが高速フーリエ変換というわけですね。

DFT ↓ 高速化 FFT

まずは離散フーリエ変換から理解しましょう。

定義

$2 π$ と書くのはちょっと長いので、 $τ = 2 π$ とします。
$ζ_{N}$ を $1$ の原始 $N$ 乗根のうちの $1$ つ、 $ζ_{N} = e^{i τ / N} = cos (\frac{τ}{N}) + i sin (\frac{τ}{N})$ とします。
例えば、 $ζ_{2} = - 1, ζ_{3} = \frac{3 - i}{2}, ζ_{4} = i, ζ_{2 N}^{2} = ζ_{N}, ζ_{N}^{N} = 1$ です。

複素平面上の単位円を $N$ 等分する点

数列 $A = (A_{0}, A_{1}, \dots, A_{N - 1})$ から $N - 1$ 次多項式 $f_{A} (x) = A_{0} + A_{1} x + \dots + A_{N - 1} x^{N - 1}$ を作ります。
畳み込みと多項式の積は対応しているので、この 2 つは同一視しがちです。

そして、 $A = (A_{0}, A_{1}, \dots, A_{N - 1})$ を $B = (f_{A} (ζ_{N}^{0}), f_{A} (ζ_{N}^{1}), \dots, f_{A} (ζ_{N}^{N - 1}))$ に変換する操作を、離散フーリエ変換と言います。

B_{0} B_{1} B_{2} = f_{A} (ζ_{N}^{0}) = ζ_{N}^{0} A_{0} + ζ_{N}^{0} A_{1} + ζ_{N}^{0} A_{2} + \dots + ζ_{N}^{0} A_{N - 1} = f_{A} (ζ_{N}^{1}) = ζ_{N}^{0} A_{0} + ζ_{N}^{1} A_{1} + ζ_{N}^{2} A_{2} + \dots + ζ_{N}^{N - 1} A_{N - 1} = f_{A} (ζ_{N}^{2}) = ζ_{N}^{0} A_{0} + ζ_{N}^{2} A_{1} + ζ_{N}^{4} A_{2} + \dots + ζ_{N}^{2 (N - 1)} A_{N - 1} ⋮

⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ B_{0} B_{1} B_{2} ⋮ B_{N - 1} ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ ζ_{N}^{0} ζ_{N}^{0} ζ_{N}^{0} ⋮ ζ_{N}^{0} ζ_{N}^{0} ζ_{N}^{1} ζ_{N}^{2} ⋮ ζ_{N}^{N - 1} ζ_{N}^{0} ζ_{N}^{2} ζ_{N}^{4} ⋮ ζ_{N}^{2 (N - 1)} \dots \dots \dots ⋱ \dots ζ_{N}^{0} ζ_{N}^{N - 1} ζ_{N}^{2 (N - 1)} ⋮ ζ_{N}^{(N - 1)^{2}} ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ A_{0} A_{1} A_{2} ⋮ A_{N - 1} ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤

離散フーリエ変換の行列表現

vector<complex<double>> DFT(vector<complex<double>> A){
    const int N = A.size();
    vector<complex<double>> B(N);
    for(int i = 0; i < N; i++) for(int j = 0; j < N; j++){
        B[i] += A[j] * polar(1, 2 * M_PI * i * j / N);
    }
    return B;
}

C++ で離散フーリエ変換

逆離散フーリエ変換

逆に、 $B = (f_{A} (ζ_{N}^{0}), f_{A} (ζ_{N}^{1}), \dots, f_{A} (ζ_{N}^{N - 1}))$ から $A = (A_{0}, A_{1}, \dots, A_{N - 1})$ を復元する操作を逆離散フーリエ変換と言います。
逆離散フーリエ変換はどのような形になっているでしょうか？

ここで、

B_{0} + B_{1} + \dots + B_{N - 1} = = (ζ_{N}^{0} + ζ_{N}^{0} + ζ_{N}^{0} + \dots + ζ_{N}^{0}) A_{0} + (ζ_{N}^{0} + ζ_{N}^{1} + ζ_{N}^{2} + \dots + ζ_{N}^{N - 1}) A_{1} + (ζ_{N}^{0} + ζ_{N}^{2} + ζ_{N}^{4} + \dots + ζ_{N}^{2 (N - 1)}) A_{2} + \dots + (ζ_{N}^{0} + ζ_{N}^{N - 1} + ζ_{N}^{2 (N - 1)} + \dots + ζ_{N}^{(N - 1)^{2}}) A_{N - 1} N A_{0}

という式が成り立っています。（ $A_{0}$ 以外の係数は複素平面上の単位円をグルグル回っているので、全部足すと $0$ ）

よって、 $A_{0} = \frac{1}{N} (B_{0} + B_{1} + \dots + B_{N - 1})$ と復元できます。
また、

ζ_{N}^{0} B_{0} + ζ_{N}^{- 1} B_{1} + \dots + ζ_{N}^{- N + 1} B_{N - 1} = = (ζ_{N}^{0} + ζ_{N}^{- 1} + ζ_{N}^{- 2} + \dots + ζ_{N}^{- N + 1}) A_{0} + (ζ_{N}^{0} + ζ_{N}^{0} + ζ_{N}^{0} + \dots + ζ_{N}^{0}) A_{1} + (ζ_{N}^{0} + ζ_{N}^{1} + ζ_{N}^{2} + \dots + ζ_{N}^{N - 1}) A_{2} + \dots + (ζ_{N}^{0} + ζ_{N}^{N - 2} + ζ_{N}^{2 (N - 2)} + \dots + ζ_{N}^{(N - 1) (N - 2)}) A_{N - 1} N A_{1}

なので、 $A_{1} = \frac{1}{N} (ζ_{N}^{0} B_{0} + ζ_{N}^{- 1} B_{1} + \dots + ζ_{N}^{- N + 1} B_{N - 1})$ と復元できます。

同様の計算により、逆離散フーリエ変換は、離散フーリエ変換の $ζ_{N}$ を $ζ_{N}^{- 1}$ に置き換えて、最後に $N$ で割ったものであることが分かります。

⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ A_{0} A_{1} A_{2} ⋮ A_{N - 1} ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ = \frac{1}{N} ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ ζ_{N}^{0} ζ_{N}^{0} ζ_{N}^{0} ⋮ ζ_{N}^{0} ζ_{N}^{0} ζ_{N}^{- 1} ζ_{N}^{- 2} ⋮ ζ_{N}^{- N + 1} ζ_{N}^{0} ζ_{N}^{- 2} ζ_{N}^{- 4} ⋮ ζ_{N}^{2 (- N + 1)} \dots \dots \dots ⋱ \dots ζ_{N}^{0} ζ_{N}^{- N + 1} ζ_{N}^{2 (- N + 1)} ⋮ ζ_{N}^{- (N - 1)^{2}} ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ B_{0} B_{1} B_{2} ⋮ B_{N - 1} ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤

逆離散フーリエ変換の行列表現

vector<complex<double>> IDFT(vector<complex<double>> B){
    const int N = B.size();
    vector<complex<double>> A(N);
    for(int i = 0; i < N; i++) for(int j = 0; j < N; j++){
        A[i] += B[j] * polar(1, -2 * M_PI * i * j / N);
    }
    for(int i = 0; i < N; i++) A[i] /= N;
    return A;
}

C++ で逆離散フーリエ変換

離散フーリエ変換を利用した畳み込み

数列 $A = (A_{0}, A_{1}, \dots, A_{∣ A ∣ - 1}), B = (B_{0}, B_{1}, \dots, B_{∣ B ∣ - 1})$ から、

C_{k} = i + j = k \sum A_{i} B_{j}

で定義される数列 $C = (C_{0}, C_{1}, \dots, C_{∣ A ∣ + ∣ B ∣ - 2})$ を作ることを畳み込みと言います。例えば、 $A = (3, 1, 4)$ と $B = (1, 5, 9)$ を畳み込むと、 $C = (3, 15 + 1, 27 + 5 + 4, 9 + 20, 36) = (3, 16, 36, 29, 36)$ となります。

畳み込みは定義式をそのまま計算することで $Θ (∣ A ∣ ∣ B ∣)$ で計算することができますが、離散フーリエ変換を経由しても計算することができます。

畳み込みと多項式の積

畳み込みの操作は、多項式の積と対応しています。

列 $X$ に対して $f_{X} (x)$ を $∣ X ∣ - 1$ 次多項式 $f_{X} (x) = X_{0} + X_{1} x + \dots + X_{∣ X ∣ - 1} x^{∣ X ∣ - 1}$ とします。

$A$ と $B$ を畳み込んで $C$ ができるとき、 $f_{A} (x) \times f_{B} (x) = f_{C} (x)$ が成り立ちます。

$\times$	$1 x^{0}$	$5 x^{1}$	$9 x^{2}$
$3 x^{0}$	$3 x^{0}$	$15 x^{1}$	$27 x^{2}$
$1 x^{1}$	$1 x^{1}$	$5 x^{2}$	$9 x^{3}$
$4 x^{2}$	$4 x^{2}$	$20 x^{3}$	$36 x^{4}$

$i + j = k$ の条件を $x$ の指数にすることで、 $x^{i}$ と $x^{j}$ を掛けたときに $x^{i + j}$ と足し算ができて、同類項が足されて畳み込みになるというわけですね。

多点評価と多項式補間

グラフ上で、 $1$ 点を通る $0$ 次多項式、 $2$ 点を通る $1$ 次多項式、 $3$ 点を通る $2$ 次多項式、… は一意に定まりますね。
$f_{C} (x)$ は $∣ A ∣ + ∣ B ∣ - 2$ 次多項式なので、 $∣ A ∣ + ∣ B ∣ - 1$ 個の点での $f_{C} (x)$ の値が分かれば $f_{C} (x)$ が分かるということになります。

$N = ∣ A ∣ + ∣ B ∣ - 1$ と置きます。
$N$ 個の点 $ζ_{N}^{0}, ζ_{N}^{1}, \dots, ζ_{N}^{N - 1}$ を選び、 $f_{C} (ζ_{N}^{0}), f_{C} (ζ_{N}^{1}), \dots, f_{C} (ζ_{N}^{N - 1})$ を求めて $C$ を復元することを考えます。これが畳み込みを高速にする秘訣です。

$f_{A} (x) \times f_{B} (x) = f_{C} (x)$ であることを思い出すと、 $f_{A} (ζ_{N}^{0}), f_{A} (ζ_{N}^{1}), \dots, f_{A} (ζ_{N}^{N - 1})$ と $f_{B} (ζ_{N}^{0}), f_{B} (ζ_{N}^{1}), \dots, f_{B} (ζ_{N}^{N - 1})$ が分かれば、 $f_{C} (ζ_{N}^{0}), f_{C} (ζ_{N}^{1}), \dots, f_{C} (ζ_{N}^{N - 1})$ は求まります。

$f_{A} (ζ_{N}^{0}), f_{A} (ζ_{N}^{1}), \dots, f_{A} (ζ_{N}^{N - 1})$ を求めるには、離散フーリエ変換です。長さ $N$ になるまで $A$ の末尾に $0$ を追加してから離散フーリエ変換をすれば $f_{A} (ζ_{N}^{0}), f_{A} (ζ_{N}^{1}), \dots, f_{A} (ζ_{N}^{N - 1})$ が出てきます。
同様にして $f_{B} (ζ_{N}^{0}), f_{B} (ζ_{N}^{1}), \dots, f_{B} (ζ_{N}^{N - 1})$ を求めて、掛け算をして $f_{C} (ζ_{N}^{0}), f_{C} (ζ_{N}^{1}), \dots, f_{C} (ζ_{N}^{N - 1})$ を求めます。
最後に、 $f_{C} (ζ_{N}^{0}), f_{C} (ζ_{N}^{1}), \dots, f_{C} (ζ_{N}^{N - 1})$ を逆離散フーリエ変換して、 $C$ が求まりました。

計算量は、離散フーリエ変換が支配的なので、ここが高速になれば高速な畳み込みが実現できそうです。

高速フーリエ変換 (FFT)

$N$ が $2$ 冪なら高速になるらしいですよ…

実験してみよう

試しに $N = 4$ のときで考えてみましょう。

B_{0} B_{1} B_{2} B_{3} = A_{0} + A_{1} + A_{2} + A_{3} = A_{0} + i A_{1} - A_{2} - i A_{3} = A_{0} - A_{1} + A_{2} - A_{3} = A_{0} - i A_{1} - A_{2} + i A_{3}

どこかまとめて計算できる場所はあるでしょうか？

$B_{0}$ と $B_{2}$ 、 $B_{1}$ と $B_{3}$ が似ていますね…

B_{0} B_{2} B_{1} B_{3} = A_{0} + A_{1} + A_{2} + A_{3} = A_{0} - A_{1} + A_{2} - A_{3} = A_{0} + i A_{1} - A_{2} - i A_{3} = A_{0} - i A_{1} - A_{2} + i A_{3}

B_{0} B_{2} B_{1} B_{3} = (A_{0} + A_{2}) + (A_{1} + A_{3}) = (A_{0} + A_{2}) - (A_{1} + A_{3}) = (A_{0} - A_{2}) + i (A_{1} - A_{3}) = (A_{0} - A_{2}) - i (A_{1} - A_{3})

$A_{0} + A_{2}, A_{0} - A_{2}, A_{1} + A_{3}, A_{1} - A_{3}$ の $4$ つにまとまりました。

$N = 8$

$N = 8$ でもやってみましょう。表記が面倒なので行列を使います。

⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ B_{0} B_{4} B_{1} B_{5} B_{2} B_{6} B_{3} B_{7} ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{4} ζ_{8}^{1} ζ_{8}^{5} ζ_{8}^{2} ζ_{8}^{6} ζ_{8}^{3} ζ_{8}^{7} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{2} ζ_{8}^{2} ζ_{8}^{4} ζ_{8}^{4} ζ_{8}^{6} ζ_{8}^{6} ζ_{8}^{0} ζ_{8}^{4} ζ_{8}^{3} ζ_{8}^{7} ζ_{8}^{6} ζ_{8}^{2} ζ_{8}^{1} ζ_{8}^{5} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{4} ζ_{8}^{4} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{4} ζ_{8}^{4} ζ_{8}^{0} ζ_{8}^{4} ζ_{8}^{5} ζ_{8}^{1} ζ_{8}^{2} ζ_{8}^{6} ζ_{8}^{7} ζ_{8}^{3} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{6} ζ_{8}^{6} ζ_{8}^{4} ζ_{8}^{4} ζ_{8}^{2} ζ_{8}^{2} ζ_{8}^{0} ζ_{8}^{4} ζ_{8}^{7} ζ_{8}^{3} ζ_{8}^{6} ζ_{8}^{2} ζ_{8}^{5} ζ_{8}^{1} ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ A_{0} A_{1} A_{2} A_{3} A_{4} A_{5} A_{6} A_{7} ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤

似ている部分を揃えて…

⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ B_{0} B_{4} B_{1} B_{5} B_{2} B_{6} B_{3} B_{7} ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{0} - ζ_{8}^{0} ζ_{8}^{1} - ζ_{8}^{1} ζ_{8}^{2} - ζ_{8}^{2} ζ_{8}^{3} - ζ_{8}^{3} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{2} ζ_{8}^{2} ζ_{8}^{4} ζ_{8}^{4} ζ_{8}^{6} ζ_{8}^{6} ζ_{8}^{0} - ζ_{8}^{0} ζ_{8}^{3} - ζ_{8}^{3} ζ_{8}^{6} - ζ_{8}^{6} ζ_{8}^{1} - ζ_{8}^{1} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{4} ζ_{8}^{4} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{4} ζ_{8}^{4} ζ_{8}^{0} - ζ_{8}^{0} ζ_{8}^{5} - ζ_{8}^{5} ζ_{8}^{2} - ζ_{8}^{2} ζ_{8}^{7} - ζ_{8}^{7} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{6} ζ_{8}^{6} ζ_{8}^{4} ζ_{8}^{4} ζ_{8}^{2} ζ_{8}^{2} ζ_{8}^{0} - ζ_{8}^{0} ζ_{8}^{7} - ζ_{8}^{7} ζ_{8}^{6} - ζ_{8}^{6} ζ_{8}^{5} - ζ_{8}^{5} ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ A_{0} A_{1} A_{2} A_{3} A_{4} A_{5} A_{6} A_{7} ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤

マイナスを取り出して…

⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ B_{0} B_{4} B_{1} B_{5} B_{2} B_{6} B_{3} B_{7} ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{2} ζ_{8}^{2} ζ_{8}^{4} ζ_{8}^{4} ζ_{8}^{6} ζ_{8}^{6} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{4} ζ_{8}^{4} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{4} ζ_{8}^{4} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{6} ζ_{8}^{6} ζ_{8}^{4} ζ_{8}^{4} ζ_{8}^{2} ζ_{8}^{2} ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ ⎣ ⎢ ⎢ ⎢ ⎡ A_{0} A_{2} A_{4} A_{6} ⎦ ⎥ ⎥ ⎥ ⎤ + ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ ζ_{8}^{0} - ζ_{8}^{0} ζ_{8}^{1} - ζ_{8}^{1} ζ_{8}^{2} - ζ_{8}^{2} ζ_{8}^{3} - ζ_{8}^{3} ζ_{8}^{0} - ζ_{8}^{0} ζ_{8}^{3} - ζ_{8}^{3} ζ_{8}^{6} - ζ_{8}^{6} ζ_{8}^{1} - ζ_{8}^{1} ζ_{8}^{0} - ζ_{8}^{0} ζ_{8}^{5} - ζ_{8}^{5} ζ_{8}^{2} - ζ_{8}^{2} ζ_{8}^{7} - ζ_{8}^{7} ζ_{8}^{0} - ζ_{8}^{0} ζ_{8}^{7} - ζ_{8}^{7} ζ_{8}^{6} - ζ_{8}^{6} ζ_{8}^{5} - ζ_{8}^{5} ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ ⎣ ⎢ ⎢ ⎢ ⎡ A_{1} A_{3} A_{5} A_{7} ⎦ ⎥ ⎥ ⎥ ⎤

同じ部分が出来ています！

⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ B_{0} B_{4} B_{1} B_{5} B_{2} B_{6} B_{3} B_{7} ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 11000000001100000000110000000011 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ ⎣ ⎢ ⎢ ⎡ ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{2} ζ_{8}^{4} ζ_{8}^{6} ζ_{8}^{0} ζ_{8}^{4} ζ_{8}^{0} ζ_{8}^{4} ζ_{8}^{0} ζ_{8}^{6} ζ_{8}^{4} ζ_{8}^{2} ⎦ ⎥ ⎥ ⎤ ⎣ ⎢ ⎢ ⎡ A_{0} A_{2} A_{4} A_{6} ⎦ ⎥ ⎥ ⎤ + ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ ζ_{8}^{0} - ζ_{8}^{0} 000000 00 ζ_{8}^{1} - ζ_{8}^{1} 0000 0000 ζ_{8}^{2} - ζ_{8}^{2} 00 000000 ζ_{8}^{3} - ζ_{8}^{3} ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ ⎣ ⎢ ⎢ ⎡ ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{2} ζ_{8}^{4} ζ_{8}^{6} ζ_{8}^{0} ζ_{8}^{4} ζ_{8}^{0} ζ_{8}^{4} ζ_{8}^{0} ζ_{8}^{6} ζ_{8}^{4} ζ_{8}^{2} ⎦ ⎥ ⎥ ⎤ ⎣ ⎢ ⎢ ⎡ A_{1} A_{3} A_{5} A_{7} ⎦ ⎥ ⎥ ⎤

同じ部分をまとめた結果、

$⎣ ⎢ ⎢ ⎢ ⎡ ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{2} ζ_{8}^{4} ζ_{8}^{6} ζ_{8}^{0} ζ_{8}^{4} ζ_{8}^{0} ζ_{8}^{4} ζ_{8}^{0} ζ_{8}^{6} ζ_{8}^{4} ζ_{8}^{2} ⎦ ⎥ ⎥ ⎥ ⎤ ⎣ ⎢ ⎢ ⎢ ⎡ A_{0} A_{2} A_{4} A_{6} ⎦ ⎥ ⎥ ⎥ ⎤$ と $⎣ ⎢ ⎢ ⎢ ⎡ ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{0} ζ_{8}^{2} ζ_{8}^{4} ζ_{8}^{6} ζ_{8}^{0} ζ_{8}^{4} ζ_{8}^{0} ζ_{8}^{4} ζ_{8}^{0} ζ_{8}^{6} ζ_{8}^{4} ζ_{8}^{2} ⎦ ⎥ ⎥ ⎥ ⎤ ⎣ ⎢ ⎢ ⎢ ⎡ A_{1} A_{3} A_{5} A_{7} ⎦ ⎥ ⎥ ⎥ ⎤$

を計算すれば良いということが分かりました。
これはなんと、離散フーリエ変換の形をしています。(すごい)
長さが半分になっていくので、 $N$ が $2$ 冪であれば、これを繰り返し適用できて、高速になりそうです。

一般化

$N$ を $2$ 冪とします。 $A = (A_{0}, A_{1}, \dots, A_{N - 1})$ を高速フーリエ変換して $B = (B_{0}, B_{1}, \dots, B_{N - 1})$ を作ります。

$A$ を奇数番目と偶数番目に分けて、 $A_{e} = (A_{0}, A_{2}, \dots, A_{N - 2}), A_{o} = (A_{1}, A_{3}, \dots, A_{N - 1})$ を作ります。
$A_{e}, A_{o}$ をそれぞれ高速フーリエ変換して、 $B_{e}, B_{o}$ とします。 (長さ $1$ の場合そのまま)
$(B_{o})_{i}$ (0-indexed) を $ζ_{N}^{i}$ 倍します。
$B_{i} = (B_{e})_{i} + (B_{o})_{i}, B_{N / 2 + i} = (B_{e})_{i} - (B_{o})_{i}$ の式で $B$ を作ります。

長さ $N$ の処理を $1$ 回、長さ $N / 2$ の処理を $2$ 回、… 、長さ $1$ の処理を $N$ 回行うので、計算量は $O (N lo g N)$ です。

vector<complex<double>> FFT(vector<complex<double>> A){
    const int N = A.size();
    if(N == 1) return A;
    vector<complex<double>> even(N / 2), odd(N / 2);
    for(int i = 0; i < N / 2; i++){
        even[i] = A[i * 2];
        odd[i] = A[i * 2 + 1];
    }
    even = FFT(even);
    odd = FFT(odd);
    for(int i = 0; i < N / 2; i++){
        odd[i] *= polar(1.0, 2 * M_PI * i / N);
        A[i] = even[i] + odd[i];
        A[N / 2 + i] = even[i] - odd[i];
    }
    return A;
}

C++ で高速フーリエ変換

FFT には定数倍高速化の技術がたくさんあり、ここから何倍か速くできるのですが、それは他の記事等に任せることにします。

逆高速フーリエ変換

高速フーリエ変換の $ζ_{N}$ を $ζ_{N}^{- 1}$ に置き換えて、最後に $N$ で割ったものが逆高速フーリエ変換です。

高速フーリエ変換を利用した畳み込み

基本的には離散フーリエ変換を利用した畳み込みと同じで、 $N$ が $2$ 冪になるように、 $N = ∣ A ∣ + ∣ B ∣ - 1$ とするのではなく、 $∣ A ∣ + ∣ B ∣ - 1$ を $2$ 冪に切り上げたものを $N$ とすれば良いです。

おわり

🎉 これであなたも FFT の理解者！ 🎉

おまけ

巡回畳み込み

離散フーリエ変換で畳み込みをするとき、 $∣ A ∣ + ∣ B ∣ - 1$ の長さを確保しますが、もしこれが足りなかったら、すなわち $N < ∣ A ∣ + ∣ B ∣ - 1$ のときどうなるでしょうか？

$f_{A} (ζ_{N}^{0}), f_{A} (ζ_{N}^{1}), \dots, f_{A} (ζ_{N}^{N - 1})$ と $f_{B} (ζ_{N}^{0}), f_{B} (ζ_{N}^{1}), \dots, f_{B} (ζ_{N}^{N - 1})$ には特に影響はないので、 $f_{C} (ζ_{N}^{0}), f_{C} (ζ_{N}^{1}), \dots, f_{C} (ζ_{N}^{N - 1})$ までは正しく計算できますね。しかし、 $f_{C}$ は $N - 1$ 次多項式として扱われ、長さ $N$ の $C$ が逆離散フーリエ変換によって出てきます。このときの $C$ はどのようなものになっているでしょうか？

例えば、 $f_{A} (x) \times f_{B} (x) = x^{N}$ のとき、 $f_{C} (ζ_{N}^{0}) = f_{C} (ζ_{N}^{1}) = \dots = f_{C} (ζ_{N}^{N - 1}) = 1$ で、これは $f_{A} (x) \times f_{B} (x) = 1$ の場合と区別ができません。そのため、 $C = (1, 0, \dots, 0)$ となります。
また、 $f_{A} (x) \times f_{B} (x) = x^{N + 1}$ のとき、 $f_{C} (ζ_{N}^{0}) = ζ_{N}^{0}, f_{C} (ζ_{N}^{1}) = ζ_{N}^{1}, \dots, f_{C} (ζ_{N}^{N - 1}) = ζ_{N}^{N - 1}$ で、これは $f_{A} (x) \times f_{B} (x) = x$ の場合と区別ができません。そのため、 $C = (0, 1, 0, \dots, 0)$ となります。

このように、 $N$ 次以上の項は、 $x^{N} = 1$ のルールにより $x^{0}$ の方から再び現れます。
このような場合の畳み込み

C_{k} = i + j = k (m o d N) \sum A_{i} B_{j}

を巡回畳み込みと言います。離散フーリエ変換は畳み込みをするための変換というより、巡回畳み込みをするための変換(十分な長さを確保することで通常の畳み込みになる)なんですね。

明日の担当は @liquid1224 さんです！楽しみ〜