高速Fourier変換
概要
高速Fourier変換（fast Fourier transform）とは、長さ $N$ の数列の離散 Fourier 変換 $X_t=\sum_k x_k\zeta_N^{-tk}$ を、$N$ を因数に分けて短い変換に帰着させることで速く計算する方法である。$N$ が偶数なら偶数番目と奇数番目の項に分けた長さ $N/2$ の変換 2 つから全体が求まり、$N=2^m$ ではこれを繰り返して、定義どおりなら $N^2$ 回かかる乗法が $\frac N2\log_2 N$ 回で済む。巡回畳み込みが変換で成分ごとの積になることと組み合わせて、多項式や大きな整数の積を $N\log N$ 程度の手間で計算でき、$\omega^{N/2}=-1$ を満たす元をもつ有限体などの環の上でも同じ計算が成り立つ。
前提知識: 離散Fourier変換と反転公式, 1の冪根, 複素数, 多項式
長さ $N$ の数列 $x_0,\dots,x_{N-1}$ の離散 Fourier 変換 $X_t=\sum_{k}x_k\zeta_N^{-tk}$ を定義どおりに計算すると、$N$ 個の値それぞれに $N$ 項の和が要るので、掛け算はおよそ $N^2$ 回になる。$N=2^{20}\approx10^6$ なら $10^{12}$ 回である。ところが $N$ が偶数なら、偶数番目と奇数番目の項に分けると、長さ $N/2$ の離散 Fourier 変換 2 つと $N/2$ 回の掛け算で全体が求まる。これを繰り返すと、$N=2^m$ では掛け算は $\frac N2\log_2N$ 回で済み、$N=2^{20}$ なら約 $10^7$ 回である。この計算法を 高速 Fourier 変換（fast Fourier transform, FFT）という。
離散 Fourier 変換は巡回畳み込みを成分ごとの積に変える。そのため FFT を使うと、多項式の積や大きな整数の積、信号のフィルタ処理が $N\log N$ 程度の手間でできる。この記事では、偶奇への分割の公式（バタフライ）と演算回数、一般の $N=N_1N_2$ への分割、ビット反転の並べ替え、多項式の積への応用を証明し、$1$ の冪根をもつ環（有限体など）でも同じ計算が成り立つことを示す。
定義と使える条件
$N$ を正の整数とし、$\zeta_N:=e^{2\pi i/N}=\cos\frac{2\pi}N+i\sin\frac{2\pi}N$ とおく。添字は $0$ から数える。
- 複素数の列 $x=(x_0,\dots,x_{N-1})$ に対し、
$$ X_t:=\sum_{k=0}^{N-1}x_k\,\zeta_N^{-tk}\qquad(t=0,1,\dots,N-1) $$
で定まる列 $X=(X_0,\dots,X_{N-1})$ を $x$ の 離散 Fourier 変換（DFT）といい、$X=\mathcal F_Nx$ と書く。$(t,k)$ 成分が $\zeta_N^{-tk}$ の $N$ 次正方行列を $F_N$ と書くと $X=F_Nx$ である。 - $N$ を因数に分け、短い離散 Fourier 変換に帰着させて $\mathcal F_Nx$ を計算する方法を 高速 Fourier 変換（FFT）という。とくに $N=2^m$ で偶数番目と奇数番目への分割（thm-fft-radix2）を繰り返すものを 基数 2 の FFT という。
この符号と係数の付け方は 離散Fourier変換と反転公式 の記事の定義「離散Fourier変換」と同じである。その記事の定理「反転公式とParsevalの等式」により
$$
x_k=\frac1N\sum_{t=0}^{N-1}X_t\,\zeta_N^{tk}
$$
で $x$ に戻る（逆離散 Fourier 変換）。$\overline{\zeta_N^{tk}}=\zeta_N^{-tk}$ なので、これは $x=\frac1N\overline{F_N\overline X}$ と書ける。したがって逆変換も、共役をとって同じ FFT を使い、$N$ で割れば計算できる。
使える条件は次のとおりである。
- 基数 2 の FFT（thm-fft-radix2、thm-fft-count）：$N=2^m$。長さが 2 の冪でないときは、$0$ を詰めて長さを延ばすか（畳み込みに使う場合。thm-fft-polymul）、一般の分割を使う。
- 一般の分割（thm-fft-mixed）：$N=N_1N_2$ と分けられること。$N$ が素数だと分割できない。
- 環の上の FFT（thm-fft-ring）：可換環 $R$ に $\omega^{N/2}=-1$ となる $\omega$ があり（$N=2^m$）、逆変換には $2$ が $R$ で可逆であること。
- 多項式の積（thm-fft-polymul）：長さ $N$ が積の項数以上であること（$0$ の詰め）。
主定理と証明
偶奇への分割
$N=2M$ とし、$x$ の偶数番目の列 $x^{\mathrm{e}}=(x_0,x_2,\dots,x_{N-2})$ と奇数番目の列 $x^{\mathrm{o}}=(x_1,x_3,\dots,x_{N-1})$ の長さ $M$ の離散 Fourier 変換を $E=\mathcal F_Mx^{\mathrm{e}}$、$O=\mathcal F_Mx^{\mathrm{o}}$ とする。このとき $t=0,1,\dots,M-1$ について
$$
X_t=E_t+\zeta_N^{-t}O_t,\qquad X_{t+M}=E_t-\zeta_N^{-t}O_t
$$
が成り立つ。
$\zeta_N^2=e^{2\pi i/M}=\zeta_M$ と $\zeta_N^{M}=e^{\pi i}=-1$ を使う。$0\le t\le N-1$ について、$k=2j$ と $k=2j+1$（$0\le j\le M-1$）に分けると
$$
X_t=\sum_{j=0}^{M-1}x_{2j}\zeta_N^{-2tj}+\sum_{j=0}^{M-1}x_{2j+1}\zeta_N^{-t(2j+1)}=\sum_{j=0}^{M-1}x_{2j}\zeta_M^{-tj}+\zeta_N^{-t}\sum_{j=0}^{M-1}x_{2j+1}\zeta_M^{-tj}
$$
である。$\zeta_M^M=1$ なので $\zeta_M^{-tj}$ は $t$ を $M$ で割った余りだけで決まり、$0\le t\le M-1$ なら右辺の 2 つの和はそれぞれ $E_t$、$O_t$ である。よって $X_t=E_t+\zeta_N^{-t}O_t$ である。$t+M$ に対しては、2 つの和は $t$ のときと同じ $E_t$、$O_t$ で、係数は $\zeta_N^{-(t+M)}=\zeta_N^{-t}\zeta_N^{-M}=-\zeta_N^{-t}$ である。よって $X_{t+M}=E_t-\zeta_N^{-t}O_t$ である。$\square$
2 つの値 $E_t,O_t$ から $E_t\pm\zeta_N^{-t}O_t$ の 2 つを作る操作を バタフライ といい、$\zeta_N^{-t}$ を 回転因子 という。行列で書けば、偶奇に並べ替える置換行列を $\Pi_N$、$\Omega_M:=\operatorname{diag}(1,\zeta_N^{-1},\dots,\zeta_N^{-(M-1)})$ として
$$
F_N=\begin{pmatrix}I_M&\Omega_M\\I_M&-\Omega_M\end{pmatrix}\begin{pmatrix}F_M&0\\0&F_M\end{pmatrix}\Pi_N
$$
である。$F_N$ は成分がすべて $0$ でない密な行列だが、$0$ の多い行列の積に分解できる。
演算回数
$N=2^m$ とする。thm-fft-radix2 を長さ $1$ まで再帰的に使って $\mathcal F_Nx$ を計算すると、複素数の乗法は $\frac N2\log_2N$ 回以下、加法と減法は合わせて $N\log_2N$ 回である。定義どおりの計算では乗法が $N^2$ 回、加法が $N(N-1)$ 回である。
長さ $N$ の変換に要する乗法の回数を $\mu(N)$、加減法の回数を $\alpha(N)$ とする。長さ $1$ の変換は $X_0=x_0$ なので $\mu(1)=\alpha(1)=0$ である。$N=2M$ のとき、長さ $M$ の変換を 2 回行い、$t=0,\dots,M-1$ について積 $\zeta_N^{-t}O_t$ を 1 回ずつ（計 $M$ 回）、和と差を 1 回ずつ（計 $2M=N$ 回）計算する。回転因子 $\zeta_N^{-t}$ はあらかじめ表にしておく。よって
$$
\mu(N)\le2\mu(N/2)+\frac N2,\qquad\alpha(N)=2\alpha(N/2)+N
$$
である。両辺を $N$ で割ると $\frac{\mu(N)}N\le\frac{\mu(N/2)}{N/2}+\frac12$、$\frac{\alpha(N)}N=\frac{\alpha(N/2)}{N/2}+1$ であり、$N=2^m$ から $1$ まで $m$ 回たどると $\frac{\mu(N)}N\le\frac m2$、$\frac{\alpha(N)}N=m$ を得る。定義どおりの計算では、$N$ 個の $X_t$ それぞれに $N$ 回の乗法と $N-1$ 回の加法を使う。$\square$
$\zeta_N^{-0}=1$ などの自明な掛け算を省けば乗法はさらに減るが、主要項は $\frac N2\log_2N$ のままである。$N=8$ なら乗法 $12$ 回（定義どおりなら $64$ 回）、$N=1024$ なら $5120$ 回（定義どおりなら $1048576$ 回）である。
一般の分割
$N=N_1N_2$ とし、添字を
$$
k=k_1+N_1k_2,\qquad t=N_2t_1+t_2\qquad(0\le k_1,t_1< N_1,\ 0\le k_2,t_2< N_2)
$$
と表す。
- 次が成り立つ。
$$ X_{N_2t_1+t_2}=\sum_{k_1=0}^{N_1-1}\zeta_{N_1}^{-t_1k_1}\Bigl[\zeta_N^{-t_2k_1}\sum_{k_2=0}^{N_2-1}x_{k_1+N_1k_2}\,\zeta_{N_2}^{-t_2k_2}\Bigr] $$
つまり、長さ $N_2$ の変換を $N_1$ 個行い、回転因子を掛け、長さ $N_1$ の変換を $N_2$ 個行えば $\mathcal F_Nx$ が求まる。 - $N=r_1r_2\cdots r_m$ と分け、1 を繰り返し、長さ $r_i$ の変換は定義どおりに計算すると、乗法の回数は $N(r_1+\cdots+r_m)+(m-1)N$ 以下である。
1：$k=k_1+N_1k_2$ は $0\le k\le N-1$ を 1 回ずつ表し、$t=N_2t_1+t_2$ も同様である。
$$
tk=N_2t_1k_1+Nt_1k_2+t_2k_1+N_1t_2k_2
$$
であり、$\zeta_N^{N}=1$、$\zeta_N^{N_2}=\zeta_{N_1}$、$\zeta_N^{N_1}=\zeta_{N_2}$ なので
$$
\zeta_N^{-tk}=\zeta_{N_1}^{-t_1k_1}\,\zeta_N^{-t_2k_1}\,\zeta_{N_2}^{-t_2k_2}
$$
となる。これを $X_t=\sum_kx_k\zeta_N^{-tk}$ に代入し、$k$ についての和を $k_1$ と $k_2$ の 2 重の和に書き直せば 1 の式を得る。
2：長さ $L$ の変換を定義どおりに計算する乗法の回数は $L^2$ である。長さ $N$ の変換を 1 で計算する乗法の回数を $T(N)$ とすると、$N=N_1N_2$ のとき $T(N)\le N_1T(N_2)+N_2T(N_1)+N$ である（最後の $N$ は回転因子の掛け算）。$m$ についての帰納法で $T(N)\le N(r_1+\cdots+r_m)+(m-1)N$ を示す。$m=1$ なら $T(r_1)=r_1^2=Nr_1$ である。$m\ge2$ なら $N_2=r_1$、$N_1=N':=r_2\cdots r_m$ とおくと、帰納法の仮定 $T(N')\le N'(r_2+\cdots+r_m)+(m-2)N'$ から
$$
T(N)\le r_1T(N')+N'r_1^2+N\le N(r_2+\cdots+r_m)+(m-2)N+Nr_1+N
$$
となり、右辺は $N(r_1+\cdots+r_m)+(m-1)N$ である。$\square$
$N=1000=2^3\cdot5^3$ なら 2 の上界は $1000\cdot21+5000=26000$ で、定義どおりの $10^6$ 回の 38 分の 1 以下である。$N$ が素数なら分割できないので、この方法では速くならない。この分割は CT65 が 2 進の計算機での実装とともに示したものである（同論文 (3)〜(9) 式、pp. 297–298）。
ビット反転の並べ替え
基数 2 の FFT を再帰を使わずに実行するときは、入力を次の順に並べ替えてから、長さ $2,4,\dots,N$ のバタフライを順に行う。$0\le k< 2^m$ の 2 進表示 $k=b_{m-1}2^{m-1}+\cdots+b_12+b_0$ の桁を逆に並べた $\operatorname{rev}_m(k):=b_02^{m-1}+b_12^{m-2}+\cdots+b_{m-1}$ を、$k$ の ビット反転 という。
$N=2^m$ とする。thm-fft-radix2 の偶奇の分割を、各段で「偶数番目を前半、奇数番目を後半に置く」として $m$ 回繰り返すと、もとの第 $k$ 項は第 $\operatorname{rev}_m(k)$ 番の位置に来る。
$m$ についての帰納法で示す。$m=0$ なら自明である。1 回目の分割で、第 $k$ 項は $b_0=0$（偶数）なら前半、$b_0=1$（奇数）なら後半に行き、その半分の中では第 $\lfloor k/2\rfloor$ 番目になる。$\lfloor k/2\rfloor=b_{m-1}2^{m-2}+\cdots+b_1$ である。残りの $m-1$ 回の分割は長さ $2^{m-1}$ の各半分の中で同じ規則で行われるので、帰納法の仮定により、半分の中の位置は $\operatorname{rev}_{m-1}(\lfloor k/2\rfloor)=b_12^{m-2}+\cdots+b_{m-1}$ になる。前半か後半かで $b_02^{m-1}$ が加わるので、全体の位置は $b_02^{m-1}+b_12^{m-2}+\cdots+b_{m-1}=\operatorname{rev}_m(k)$ である。$\square$
$N=8$ では、並べ替えたあとの順は $x_0,x_4,x_2,x_6,x_1,x_5,x_3,x_7$ である。並べ替えたあとは、隣り合う 2 項、続いて 4 項のまとまり、… の順にバタフライをかければよく、計算結果をもとの場所に上書きできる（CT65 pp. 299–300 は、入力をもとの順に置いて上書きしながら計算し、出力がビット反転の順に並ぶ形を、2 進の計算機向けに述べている）。
環の上の FFT
thm-fft-radix2 の証明で使ったのは $\zeta_N^2=\zeta_M$ と $\zeta_N^M=-1$ だけである。そこで、可換環 $R$ と $\omega\in R$ について、$x\in R^N$ の変換を $X_t:=\sum_kx_k\omega^{-tk}$ と定める（$\omega$ は可逆とする）。
$R$ を可換環、$N=2^m$（$m\ge1$）、$\omega\in R$ が $\omega^{N/2}=-1$ を満たすとする。
- $\omega$ は可逆で、$\omega$ と $\omega^2$ について thm-fft-radix2 と同じ式（$\zeta_N$ を $\omega$、$\zeta_M$ を $\omega^2$ に替えたもの）が成り立つ。したがって thm-fft-count と同じ回数の $R$ の演算で変換が計算できる。
- 整数 $s$ について、$\sum_{j=0}^{N-1}\omega^{sj}$ は $N\mid s$ なら $N\cdot1_R$、そうでなければ $0$ である。
- $2$ が $R$ で可逆なら、変換は全単射で、逆は $x_k=N^{-1}\sum_tX_t\,\omega^{tk}$ である。
1：$\omega^N=(\omega^{N/2})^2=1$ なので $\omega\cdot\omega^{N-1}=1$ であり、$\omega$ は可逆である。prf-fft-radix2 の計算は、$\omega^N=1$（指数を $N$ で割った余りで読めること）と $\omega^{N/2}=-1$ だけを使うので、そのまま成り立つ。$\omega^2$ についても $(\omega^2)^{N/4}=-1$（$N\ge4$ のとき）なので、再帰的に同じ式が使える。
2：$N\mid s$ なら各項が $1$ なので和は $N\cdot1_R$ である。$N\nmid s$ とし、$s=2^ac$（$c$ は奇数、$0\le a< m$。$s=0$ は除かれている）と書く。$h:=2^{m-1-a}$ とおくと $\omega^{sh}=(\omega^{N/2})^{c}=(-1)^c=-1$ である。$c':=\omega^s$ とおくと $c'^{2h}=1$ なので、$0,\dots,N-1$ を長さ $2h$ の区間（$2h=2^{m-a}$ は $N$ を割る）に分けると、各区間の中で第 $j$ 項と第 $j+h$ 項は $c'^{j+h}=-c'^{j}$ で打ち消し合う。よって和は $0$ である。
3：$\sum_tX_t\omega^{tk}=\sum_lx_l\sum_t\omega^{t(k-l)}$ であり、2 により内側の和は $l=k$ のとき $N$、ほかは $0$ である（$\lvert k-l\rvert< N$）。$N=2^m$ は可逆なので、$x_k=N^{-1}\sum_tX_t\omega^{tk}$ である。逆向きの合成も同じ計算で恒等写像になるので、変換は全単射である。$\square$
$R=\mathbb{Z}/p\mathbb{Z}$（$p$ は奇素数）で使うものを 数論変換 という。たとえば $p=41$ では $9^2=81\equiv-1$ なので $N=4$、$\omega=9$ がとれる。浮動小数点数の丸めがなく、整数の係数の積を正確に計算できる（ex-fft-ntt）。この節の内容は Sho08 §17.6 の Exercise 17.21–17.23（pp. 480–481）に、$\omega^{N/2}=-1$ を満たす $\omega$ を「原始 $N$ 乗根」と呼ぶ形で述べられている。
多項式の積
2 つの列 $a,b\in\mathbb{C}^N$ の 巡回畳み込み を $(a\ast b)_k:=\sum_{j=0}^{N-1}a_jb_{(k-j)\bmod N}$ と定める。離散Fourier変換と反転公式 の記事の命題「畳み込みは変換で積になる」により $\mathcal F_N(a\ast b)=\mathcal F_Na\cdot\mathcal F_Nb$（成分ごとの積）である。
$f(x)=\sum_{j=0}^{n_1-1}a_jx^j$、$g(x)=\sum_{j=0}^{n_2-1}b_jx^j$ を複素数係数の多項式とし、$fg=\sum_{k=0}^{n_1+n_2-2}c_kx^k$ とする。$N\ge n_1+n_2-1$ とし、$a,b$ の後ろに $0$ を詰めて長さ $N$ の列にする。このとき
$$
(c_0,\dots,c_{N-1})=\mathcal F_N^{-1}\bigl(\mathcal F_Na\cdot\mathcal F_Nb\bigr)
$$
である（$k>n_1+n_2-2$ では $c_k=0$ とする）。$N=2^m$ なら、右辺は 3 回の FFT と $N$ 回の積、すなわち乗法 $\frac32N\log_2N+N$ 回以下（ほかに $N$ での割り算が $N$ 回）で計算できる。
多項式の積の係数は $c_k=\sum_{j=0}^{k}a_jb_{k-j}$ である（$a_j=0$（$j\ge n_1$）、$b_j=0$（$j\ge n_2$）と読む）。一方、詰めた列の巡回畳み込みは
$$
(a\ast b)_k=\sum_{j=0}^{k}a_jb_{k-j}+\sum_{j=k+1}^{N-1}a_jb_{k-j+N}\qquad(0\le k\le N-1)
$$
である。2 つ目の和の項が $0$ でないには $j\le n_1-1$ かつ $k-j+N\le n_2-1$ が要る。この 2 つと $k\ge0$ から $N\le n_2-1+(j-k)\le n_2-1+(n_1-1)=n_1+n_2-2$ となり、$N\ge n_1+n_2-1$ に反する。よって 2 つ目の和は $0$ で、$(a\ast b)_k=c_k$ である。上の命題「畳み込みは変換で積になる」と反転公式から、$c=a\ast b=\mathcal F_N^{-1}(\mathcal F_Na\cdot\mathcal F_Nb)$ である。回数は、FFT 2 回、成分ごとの積 $N$ 回、逆変換 1 回（共役と FFT と $N$ での割り算。割り算は積に合わせて数えない）を thm-fft-count で数えたものである。$\square$
定義どおりの多項式の積は $n_1n_2$ 回の乗法を使う。$n_1=n_2=n$ なら $n^2$ 回で、FFT による方法は $N<4n$ にとれるので $O(n\log n)$ 回で済む。同じ式は thm-fft-ring の 3 の条件の下で、環 $R$ の上でも成り立つ。命題「畳み込みは変換で積になる」の証明は和の変数の取り替えだけで $\zeta^N=1$ しか使わないので $\omega$ でもそのまま通り、逆変換は thm-fft-ring の 3 が与える。
公式の表
| 公式 | 内容 | 使える条件 | 根拠 |
|---|---|---|---|
| 変換 | $X_t=\sum_kx_k\zeta_N^{-tk}$ | $N\ge1$ | def-fft-main |
| 逆変換 | $x_k=\frac1N\sum_tX_t\zeta_N^{tk}=\frac1N\overline{\bigl(F_N\overline X\bigr)}_k$ | $N\ge1$ | 離散Fourier変換と反転公式 |
| バタフライ | $X_t=E_t+\zeta_N^{-t}O_t$、$X_{t+N/2}=E_t-\zeta_N^{-t}O_t$ | $N$ が偶数 | thm-fft-radix2 |
| 回数（基数 2） | 乗法 $\le\frac N2\log_2N$、加減法 $N\log_2N$ | $N=2^m$ | thm-fft-count |
| 一般の分割 | 長さ $N_2$ の変換 $N_1$ 個 → 回転因子 → 長さ $N_1$ の変換 $N_2$ 個 | $N=N_1N_2$ | thm-fft-mixed |
| 並べ替え | 第 $k$ 項を第 $\operatorname{rev}_m(k)$ 番へ | $N=2^m$ | prop-fft-bitrev |
| 畳み込み | $\mathcal F_N(a\ast b)=\mathcal F_Na\cdot\mathcal F_Nb$ | 巡回畳み込み | 離散Fourier変換と反転公式 |
| 多項式の積 | $c=\mathcal F_N^{-1}(\mathcal F_Na\cdot\mathcal F_Nb)$ | $N\ge n_1+n_2-1$ | thm-fft-polymul |
| 環の上 | $\zeta_N$ を $\omega$ に替える | $\omega^{N/2}=-1$、逆には $2\in R^{\times}$ | thm-fft-ring |
計算の手順
$N=2^m$ の列 $x$ の変換 $X=\mathcal F_Nx$ を、上書きしながら計算する手順は次のとおりである。
- 長さが 2 の冪でなければ、目的に応じて $0$ を詰める（畳み込みに使うときは thm-fft-polymul の長さ以上に）。
- 回転因子 $w_L:=\zeta_L^{-1}=e^{-2\pi i/L}$ の冪を $L=2,4,\dots,N$ について表にしておく。
- 配列 $a$ に $a_{\operatorname{rev}_m(k)}:=x_k$ と並べ替えて入れる（prop-fft-bitrev）。
- $s=1,2,\dots,m$ の順に、$L=2^s$、$h=L/2$ とし、先頭が $L$ の倍数の位置 $b$ から始まる長さ $L$ の各まとまりで、$j=0,\dots,h-1$ について $u=a_{b+j}$、$v=w_L^ja_{b+j+h}$ とおき、$a_{b+j}:=u+v$、$a_{b+j+h}:=u-v$ とする（thm-fft-radix2）。
- 終わったとき $a=X$ である。逆変換は、$X$ の共役をとって 3〜4 を行い、結果の共役を $N$ で割る。
手順 4 の第 $s$ 段が終わった時点で、長さ $2^s$ の各まとまりには、もとの列から添字を $2^{m-s}$ で割った余りが等しい $2^s$ 個の項を順に取り出した部分列の、長さ $2^s$ の変換が入っている。これは thm-fft-radix2 と prop-fft-bitrev を $s$ についての帰納法で組み合わせればわかる。
例題
$x=(1,2,3,4)$ の変換を thm-fft-radix2 で計算する（定義どおりの計算は 離散Fourier変換と反転公式 の記事の例「(1, 2, 3, 4) を手で変換する」にある）。
答え：$X=(10,\ -2+2i,\ -2,\ -2-2i)$。
途中の計算を開く
偶数番目 $(1,3)$ と奇数番目 $(2,4)$ の長さ 2 の変換は $E=(1+3,\ 1-3)=(4,-2)$、$O=(2+4,\ 2-4)=(6,-2)$ である（$\zeta_2^{-1}=-1$）。$\zeta_4^{-1}=-i$ なので $$X_0=E_0+O_0=10,\quad X_1=E_1+(-i)O_1=-2+2i,\quad X_2=E_0-O_0=-2,\quad X_3=E_1-(-i)O_1=-2-2i$$ である。乗法は自明でないものが $(-i)\cdot(-2)$ の 1 回だけである。
$x=(1,1,1,1,0,0,0,0)$ の長さ 8 の変換を、上の計算の手順のとおりに計算する。
答え：$X_0=4$、$X_2=X_4=X_6=0$ と
$$
X_1=1-(1+\sqrt2)i,\quad X_3=1-(\sqrt2-1)i,\quad X_5=1+(\sqrt2-1)i,\quad X_7=1+(1+\sqrt2)i
$$
（$X_1\approx1-2.41421i$、$X_3\approx1-0.41421i$）。
途中の計算を開く
並べ替え：$(x_0,x_4,x_2,x_6,x_1,x_5,x_3,x_7)=(1,0,1,0,1,0,1,0)$。
第 1 段（$L=2$、回転因子 $1$）：各組 $(1,0)$ が $(1+0,1-0)=(1,1)$ になり、配列は $(1,1,1,1,1,1,1,1)$。
第 2 段（$L=4$、回転因子 $1,-i$）：各まとまり $(1,1,1,1)$ で $u=1$、$v=1$ と $u=1$、$v=-i$ から $(2,\ 1-i,\ 0,\ 1+i)$。配列は $(2,1-i,0,1+i,2,1-i,0,1+i)$。
第 3 段（$L=8$、回転因子 $w=e^{-\pi i/4}=\frac{1-i}{\sqrt2}$ の冪）：$j=0$ で $2\pm2$ から $X_0=4$、$X_4=0$。$j=1$ で $v=w(1-i)=\frac{(1-i)^2}{\sqrt2}=-\sqrt2\,i$ から $X_1=1-i-\sqrt2\,i$、$X_5=1-i+\sqrt2\,i$。$j=2$ で $v=w^2\cdot0=0$ から $X_2=X_6=0$。$j=3$ で $w^3=\frac{-1-i}{\sqrt2}$、$v=w^3(1+i)=\frac{-(1+i)^2}{\sqrt2}=-\sqrt2\,i$ から $X_3=1+i-\sqrt2\,i$、$X_7=1+i+\sqrt2\,i$。
閉じた形で確かめると、$t\ne0$ について $X_t=\sum_{k=0}^3\zeta_8^{-tk}=\frac{1-\zeta_8^{-4t}}{1-\zeta_8^{-t}}$ で、$t$ が偶数なら分子が $0$、奇数なら $\frac2{1-\zeta_8^{-t}}=1-i\cot\frac{\pi t}8$ である（$\cot\frac\pi8=1+\sqrt2$）。
$f(x)=1+2x+3x^2$、$g(x)=4+5x$ の積を、$N=4$（$\ge3+2-1$）の FFT で計算する。
答え：$fg=4+13x+22x^2+15x^3$。
途中の計算を開く
$a=(1,2,3,0)$、$b=(4,5,0,0)$ の変換は、ex-fft-n4 と同じ手順で $\mathcal F_4a=(6,\ -2-2i,\ 2,\ -2+2i)$、$\mathcal F_4b=(9,\ 4-5i,\ -1,\ 4+5i)$。成分ごとの積は $(54,\ -18+2i,\ -2,\ -18-2i)$。逆変換（共役をとって変換し、共役を $4$ で割る）で $(4,13,22,15)$ を得る。たとえば第 0 成分は $\frac14(54-18+2i-2-18-2i)=4$。
ex-fft-polymul と同じ積を $\mathbb{F}_{41}=\mathbb{Z}/41\mathbb{Z}$ の上で、$N=4$、$\omega=9$（$9^2=81\equiv-1$）で計算する。$\omega^{-1}=32$（$9\cdot32=288=7\cdot41+1$）、$4^{-1}=31$（$4\cdot31=124=3\cdot41+1$）である。
答え：$\mathcal F_4a=(6,21,2,16)$、$\mathcal F_4b=(9,0,40,8)$、積は $(13,0,39,5)$、逆変換は $31\cdot(16,11,6,19)\equiv(4,13,22,15)$ で、係数がどれも $41$ 未満なので整数の係数がそのまま得られる。
途中の計算を開く
$\mathcal F_4a$ の第 $t$ 成分は $\sum_ka_k\omega^{-tk}=\sum_ka_k32^{tk}$ で、$32^2\equiv40\equiv-1$、$32^3\equiv-32\equiv9$。$t=1$：$1+2\cdot32+3\cdot40=185\equiv21$。$t=2$：$1-2+3=2$。$t=3$：$1+2\cdot9+3\cdot40=139\equiv16$。複素数の場合の $-2-2i$ で $i$ を $9$ に替えると $-2-18=-20\equiv21$ となり、対応が見える。$\mathcal F_4b$ も同様で、$4-5i$ に当たる $4-45=-41\equiv0$ が現れる。逆変換は $\omega=9$ の冪で同じ計算をし、$31$ を掛ける。
$1234\times5678$ を、桁を係数とする多項式 $f(x)=4+3x+2x^2+x^3$、$g(x)=8+7x+6x^2+5x^3$ の積として計算する（$x=10$ を代入すると $f(10)=1234$、$g(10)=5678$）。$N=8\ge4+4-1$ の FFT で積の係数を求めると $(32,52,61,60,34,16,5)$ である（掛け算の筆算と畳み込み の筆算の各列の和に当たる）。下の位から繰り上げると、$32\to$ 位 $2$・繰り上がり $3$、$52+3=55\to5$・$5$、$61+5=66\to6$・$6$、$60+6=66\to6$・$6$、$34+6=40\to0$・$4$、$16+4=20\to0$・$2$、$5+2=7$ で、答えは $7006652$ である。浮動小数点数で FFT を行うと係数に小さな誤差が入りうるので、最後に最も近い整数に丸めてから繰り上げる。ex-fft-ntt のように有限体の上で計算すれば丸めは起きない。
使える条件と反例
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| $N$ が偶数 | $N=3$ | 半分の長さの 2 つの変換への分割（thm-fft-radix2） |
| $N\ge n_1+n_2-1$（$0$ の詰め） | $(1+x)^2$ を $N=2$ で計算 | 積の係数が得られること（thm-fft-polymul） |
| $\omega^{N/2}=-1$ | $R=\mathbb{C}$、$N=4$、$\omega=-1$ | 変換の単射性と反転公式（thm-fft-ring の 3） |
| $2$ が $R$ で可逆 | $R=\mathbb{Z}/8\mathbb{Z}$、$N=2$、$\omega=-1$ | 変換の単射性と反転公式（thm-fft-ring の 3） |
| 回転因子の向き $\zeta_N^{-t}$ | $X_t=E_t+\zeta_N^{t}O_t$ で計算する | $\mathcal F_Nx$ が得られること（ex-fft-n4 で $X_1=-2-2i$ になる） |
どの反例も、表の左の列の条件だけを破っている。
計算を開く
1 行目：$N=3$ では偶数番目 $(x_0,x_2)$ と奇数番目 $(x_1)$ の長さがそろわず、証明で使った $\zeta_N^{N/2}=-1$ に当たるものがない。$3$ は素数なので thm-fft-mixed の分割もできない。
2 行目：$a=b=(1,1)$ の巡回畳み込みは $(1\cdot1+1\cdot1,\ 1\cdot1+1\cdot1)=(2,2)$ で、$(1+x)^2=1+2x+x^2$ の係数 $(1,2,1)$ と違う。$x^2$ の項が $x^0$ の位置に回り込んだ。$N=3$ に詰めれば $(1,2,1)$ が得られる。
3 行目：$(-1)^2=1\ne-1$。離散Fourier変換と反転公式 の記事の例「反例：原始的でない 1 の冪根では戻せない」のとおり、$(1,0,-1,0)$ と $(0,0,0,0)$ がどちらも $0$ に移る。
4 行目：$(-1)^1=-1$ なので $\omega^{N/2}=-1$ は満たすが、$2$ は $\mathbb{Z}/8\mathbb{Z}$ で可逆でない。変換は $(x_0,x_1)\mapsto(x_0+x_1,\ x_0-x_1)$ で、$(0,0)$ と $(4,4)$ がどちらも $(0,0)$ に移る。
5 行目：$X_1=E_1+iO_1=-2+i\cdot(-2)=-2-2i$ で、正しい値 $-2+2i$ の共役になる。これは $\zeta_N^{t}$ を使った変換、すなわち逆変換の $N$ 倍を計算したことになる。
よくある誤り
| 誤り | 正しくは | なぜ |
|---|---|---|
| 逆変換で $\frac1N$ を忘れる、または両方に掛ける | この記事の規約では逆変換だけに $\frac1N$ | 離散Fourier変換と反転公式 の反転公式 |
| 長さが足りないまま畳み込む | 積の項数 $n_1+n_2-1$ 以上に $0$ を詰める | ex-fft-counterexamples の 2 行目 |
| 上書き型の FFT で入力を並べ替えない | ビット反転の順に並べ替えてからバタフライ | prop-fft-bitrev |
| どんな $N$ でも $N\log N$ で済むとする | 分割できるのは $N$ が合成数のとき。素数では速くならない | thm-fft-mixed |
| 文献ごとの符号の違いを無視する | $e^{+2\pi itk/N}$ を変換に使う流儀では、逆変換の符号が入れ替わる | def-fft-main |
補足
変換の指数の符号を $+$ にする流儀や、$\frac1{\sqrt N}$ を変換と逆変換の両方に掛ける流儀もある。後者では $F_N/\sqrt N$ がユニタリ行列になる（ユニタリ行列 の記事の例「離散 Fourier 変換の行列」）。どの流儀でも、thm-fft-radix2 の式は回転因子の符号と全体の定数を付け替えるだけで成り立つ。入力の偶奇で分ける代わりに出力の添字の偶奇で分けることもでき、$N=2M$ のとき prf-fft-radix2 と同じ計算で
$$
X_{2s}=\sum_{k=0}^{M-1}(x_k+x_{k+M})\zeta_M^{-sk},\qquad X_{2s+1}=\sum_{k=0}^{M-1}(x_k-x_{k+M})\zeta_N^{-k}\zeta_M^{-sk}
$$
となる。前半と後半の和と差を先にとり、回転因子を掛けてから長さ $M$ の変換を 2 つ行う形である。これは thm-fft-mixed で $N_1=M$、$N_2=2$ とした場合にあたる（thm-fft-radix2 は $N_1=2$、$N_2=M$ の場合）。
関連項目
- 前提: 離散Fourier変換と反転公式, 1の冪根, 複素数, 多項式
- 理論: 畳み込み, ユニタリ行列, 1の冪根で数を振り分ける
- 比較: 掛け算の筆算と畳み込み, Fourier変換, Fourier級数
- 発展: 離散Fourier変換, 多倍長演算, LU分解, 特異値分解
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
