高速フーリエ変換（FFT）の分解

$F_{64} = \begin{bmatrix}I & D\\I & -D\end{bmatrix}\begin{bmatrix}F_{32} & 0\\0 & F_{32}\end{bmatrix}P$ と書き、$P$ が偶奇の置換、$D$ が $\mathrm{diag}(1, w, \ldots, w^{31})$ であることを確認して、$(w_{64})^2 = w_{32}$ を書き留めましょう。

1 段分の掛け算を $2 \cdot 32^2 + 32$ 回と数えましょう。続いて $\log_2 n$ 段の再帰をたどり、各段の掛け算が $n/2$ 回なので合計が $\frac{1}{2}n\log_2 n$ 回となり、$n^2$ 回に取って代わることを示しましょう。

$n^2 \approx 1{,}000{,}000$ と $\frac{1}{2} \cdot 1024 \cdot 10 \approx 5{,}000$ を比べ、高速化の倍率がおよそ $200$ になることを書き留めましょう。