掛け算の速さの限界（n log nの掛け算）

掛ける2つの数を$n$ビットとし、1ビットどうしの演算の回数で手間$M(n)$を数える。手順1〜4がカラツバの方法、手順5〜8がFFT、手順9から先で2つの上界を比べる。

1. $B=2^{n/2}$とおき、$x=x_{1}B+x_0$, $y=y_{1}B+y_0$と上と下の半分に分けて展開する。

   $$xy=x_1{y}_1{B}^2+(x_1{y}_0+x_0{y}_1)B+x_0{y}_0$$

2. 真ん中の係数は和どうしの積1回から求まる。

   $$x_1{y}_0+x_0{y}_1=(x_1+x_0)(y_1+y_0)-x_1{y}_1-x_0{y}_0$$

3. 半分の長さの掛け算は4回から3回に減る。残りの足し算と引き算と桁ずらしは、$n$に比例する手間$cn$で済む。

   $$K(n)=3K\left(\frac{n}{2}\right)+cn$$

4. $k$段目には長さ$n/2^k$の掛け算が$3^k$個並び、その段で足し算にかかる手間は$cn(3/2{)}^k$になる。${\log }_{2}n$段で長さが1になるので、全部を足すと次のようになる。

   $$K(n)=2cn\left({\left(\frac{3}{2}\right)}^{{\log }_{2}n}-1\right)+3^{{\log }_{2}n}K(1)=O(n^{{\log }_{2}3})$$

5. FFTの方法では、掛け算を数列の畳み込みとみる。$s$ビットずつの塊に分けて$x={\sum }_i{a}_i{2}^{si}$, $y={\sum }_j{b}_j{2}^{sj}$と書くと、積の係数は次の和になる。繰り上げは最後にまとめてする。

   $$xy=\sum _k{z}_k{2}^{sk},z_k=\sum _{i+j=k}{a}_i{b}_j$$

6. 0を足して並びを塊の個数の2倍以上に延ばし、その長さを$N$として、$\omega =e^{2\pi i/N}$で離散フーリエ変換する。${\omega }^N=1$なので${\omega }^{ik}{\omega }^{jk}={\omega }^{(i+j)k}$の指数は$N$で割った余りで足され、畳み込みは成分ごとの積に変わる。

   $${\hat{a}}_k=\sum _{j=0}^{N-1}{a}_j{\omega }^{jk},{\hat{z}}_k={\hat{a}}_k{\hat{b}}_k$$

7. ${\omega }^{N/2}=-1$を使うと、長さ$N$の変換は長さ$N/2$の2つに分かれる。$E_k$は偶数番目の項だけの変換、$O_k$は奇数番目の項だけの変換で、どちらも${\omega }^2$を1の$N/2$乗根として計算する。

   $${\hat{a}}_k=E_k+{\omega }^k{O}_k,{\hat{a}}_{k+N/2}=E_k-{\omega }^k{O}_k$$

8. 半分に分け続けると、変換の手間は次のように抑えられる。

   $$F(N)=2F\left(\frac{N}{2}\right)+O(N)=O(N\log N)$$

9. 成分の積はまた小さな整数の掛け算になる。シェーンハーゲとシュトラッセンの2つ目の方法で$2^n+1$で割った余りの掛け算の手間を$M_1(n)$とすると、長さ$n$の掛け算は、長さ$n^{\prime }=O(\sqrt{n})$の掛け算およそ$2n/n^{\prime }$個に変わる。

   $$M_1(n)<\frac{2n}{n^{\prime }}{M}_1(n^{\prime })+O(n\log n)$$

10. $T(n)=M_1(n)/(n\log n)$とおき、両辺を$n\log n$で割る。$\log n^{\prime }$はほぼ$\frac{1}{2}\log n$なので、係数の2と$\frac{1}{2}$が打ち消し合う。つまり、1段ごとの倍率はほぼ1になる。

    $$T(n)<T(n^{\prime })+C$$

11. 段を1つ下りるごとに$T$は$C$ずつ増え、平方根をとって小さくしていく段の数は${\log }_2{\log }_{2}n$ほどある。

    $$M(n)=O(n\log n\log \log n)$$

12. ハーヴィーらは、長さ$n$の掛け算を、$d$次元の離散フーリエ変換を使って、長さ$n^{\prime }=n^{1/d+o(1)}$の掛け算に分けた。論文の式（1.3）は次の形をしている。

    $$M(n)<\frac{Kn}{n^{\prime }}M(n^{\prime })+O(n\log n)$$

13. 同じく$T(n)=M(n)/(n\log n)$として割ると、$\log n^{\prime }/\log n$はほぼ$1/d$なので、係数は$K/d$ほどになる。論文は$K=1728$で成り立つことを示し、$d=1729$とおいて、$n\ge n_0=2^{1729^{12}}$のとき次を得た。

    $$T(n)<0.9998T(n^{\prime })+A$$

14. $n<n_0$での$T$の最大値を$B$とし、$C=\max (B,5000A)$とおく。$T(n^{\prime })\le C$なら$T(n)<0.9998C+0.0002C=C$なので、帰納法で$T(n)$はいつも$C$以下にとどまる。

    $$M(n)=O(n\log n)$$

1段の倍率$q$を1にすると、$T$は段の数だけ増え続ける。これが手順11の$\log \log n$の正体である。$q$を1より少しでも小さくすれば、$T$は$A/(1-q)$で頭打ちになる。画面では$A=1$なので、$q=0.9998$なら上限は5000になる。

手順12の$d$次元の変換をどう作るかに、論文の新しさがある。塊の数を$d$個の異なる素数$s_1,\dots ,s_d$の積にとると、中国剰余定理によって、1次元の畳み込みが$s_1\times \cdots \times s_d$の格子上の畳み込みに組み替わる。ただ、各辺の長さが素数のままでは、半分に分け続けるFFTが使えない。

そこで2人は、$s_i$より少し大きい2の累乗$t_i$を選び、格子の値を、ガウス関数で重みをつけて$t_1\times \cdots \times t_d$の格子へ写した。ガウス関数のフーリエ変換はまたガウス関数になるので、写した先で変換した値から、もとの変換を連立方程式で取り戻せる。2人はこれを「ガウスの再標本化」と呼んでいる。2の累乗にそろった変換はブルースタインの方法で掛け算の形に直し、ヌスバウマーの高速多項式変換で計算する。この変換は複素数の足し算と引き算だけでできている。

1729は、$K=1728=12^3$より大きい整数なら何でもよかった。論文は「$K$より大きいどの定数でもよい」と書き、5.4節の工夫を重ねて$K$を8まで下げれば$d\ge 9$で同じ結論になる、としている。ちなみに1729は、$1^3+12^3=9^3+10^3$と立方数の和で2通りに書ける数でもある。