Toom-Cook法
梅谷 武
作成：2001-02-24 更新：2006-01-12
多倍長整数の高速乗算法であるToom-Cook法についてわかりやすく解説する。
IMS:20010224001; NDC:418; keywords:Toom-Cook法;
Toom-Cook法を理解するには、ほんの少しですが組み合わせ数学の知識があった方がいいかもしれません。記号の定義も兼ねて、順列と組み合わせから復習してみましょう。
定義1.2 (第1種Stirling数)
P(n,k)を
nに関する多項式として考えて展開する。
| | |
| | | s(k,k)xk | + | s(k,k-1)xk-1 | + | … | + | s(k,1)x | + | s(k,0) |
|
この係数
s(k,i),i=0,…,kを第1種Stirling数と呼ぶ。
定理1.5 (２項定理)
正の整数
n>0について、
x,yを変数とする恒等式
が成り立つ。この式により
C(n,k)を２項係数と呼ぶ。
この性質によって、任意の２項係数を加法だけを使って計算することができます。この算法を図形的に表現したものが、いわゆるPascalの三角形です。Toomの算法を図形的に表現すると、やはりToomの三角形ともいえる図形になります。
補題1.9
第2種Stirling数について次式が成り立つ。
| S(n,k) | = | n-1
Σ
i=0 | C(n-1,i)S(i,k-1) | , | n≧1 |
補題1.10
第2種Stirling数について次式が成り立つ。
| xn | = | n
Σ
k=1 | S(n,k)P(x,k) | , | n≧1, | xは変数 |
補題1.11
第2種Stirling数について次式が成り立つ。
| S(n,k) | = | | 1
k! | k
Σ
i=1 | (-1)k-iC(k,i)in | , | n≧k≧1 |
Knuth[
S2]によれば、
Toom-Cook法は
Karatsuba法が発表された翌年の1963年にやはりソ連の
A. L. Toomによって基本的な考え方が発表され、その後、1966年にハーバード大学の
S. A. Cookにより実際の計算機で作譜する方法が示されました。米ソ冷戦時代のこの時期、この分野においてはソ連が先行し、米国が追いかけていたようにも見えます。
K>0とし、正の整数
a,bが、基数
P=2Kにより次のように
P進表現されるものとします。
ここで、多項式
を考え、その積を
とします。
Toom-Cook法は
2r+1個の値、
から
c(x)の係数を計算し、それに基数
P=2Kを代入することによって積
abを求めます。
まず、
m=2r+1とおき多項式
c(x)を
と
P(x,i)で展開します。ここで、
a(x),b(x)の係数が負でないことから
c(x)の係数も負ではなく、さらに
θi,i=0,…m-1も負でないことに注意してください。このことが
Toom-Cook法の途中の計算結果が負でないことを保証することになります。
補題2.1
P(x,k)に関して次式が成り立つ。
| P(x+1,k) | - | P(x,k) | = | kP(x,k-1), | k≧1 |
証明 k=1のとき、
k>1のとき、
| | | (x+1)x(x-1)…(x-k+2) | - | x(x-1)…(x-k+1) |
|
| | | x(x-1)…(x-k+2)(x+1-(x-k+1)) |
|
| | |
■
補題2.2
c(x)に関して次式が成り立つ。
| c(x+1) | - | c(x) | = | m-1
Σ
i=1 | iθiP(x,i-1) |
定義2.3
多項式
c(x) = cm-1xm-1 + … + c1x + c0が与えられたとき、
| Ψc(x,k) | = | | 1
k! | k
Σ
i=0 | (-1)iC(k,i)c(x+k-i) | , | k≧0 |
と定義する。
補題2.4
これまでの仮定の下で次式が成り立つ。
| Ψc(x,k+1) | = | | 1
k+1 | (Ψc(x+1,k) | - | Ψc(x,k)), | k≧0 |
証明 定義から、
| Ψc(x,k+1) | = | | 1
(k+1)! | k+1
Σ
i=0 | (-1)iC(k+1,i)c(x+k+1-i) | , | k≧0 |
である。
を使って、
| | | 1
(k+1)! | ( | k
Σ
i=1 | (-1)i(C(k,i)+C(k,i-1))c(x+k+1-i) | + | (-1)k+1c(x) | + | (-1)0c(x+k+1) | ) |
|
| | | 1
(k+1)! | ( | k
Σ
i=0 | (-1)iC(k,i)c(x+k+1-i) | - | k
Σ
j=0 | (-1)jC(k,j)c(x+k-j) | ) |
|
| | | 1
k+1 | ( | | 1
k! | k
Σ
i=0 | (-1)iC(k,i)c((x+1)+k-i) | - | | 1
k! | k
Σ
j=0 | (-1)jC(k,j)c(x+k-j) | ) |
|
■
証明 帰納法による。
k=0のとき
k=1のときは補題[
2.2]を使う。
kで正しいとして
k+1で成り立つことを示す。
| | |
| | | 1
k+1 | ( | m-1
Σ
i=k | C(i,k)θiP(x+1,i-k) | - | m-1
Σ
i=k | C(i,k)θiP(x,i-k) | ) |
|
| | | 1
k+1 | m-1
Σ
i=k+1 | C(i,k)θi(P(x+1,i-k)-P(x,i-k) |
|
| | | 1
k+1 | m-1
Σ
i=k+1 | C(i,k)θi(i-k)P(x,i-(k+1)) |
|
| | m-1
Σ
i=k+1 | C(i,k+1)θiP(x,i-(k+1)) |
|
■
これで
Toomの三角形を描く準備ができました。
r=2のときを考えます。まず
を計算し、これを利用して次の行列を計算します。
１列目はすでに計算されています。２列目以降は
| Ψc(x,k+1) | = | | 1
k+1 | (Ψc(x+1,k) | - | Ψc(x,k)) |
によって計算します。k+1列目の値は、k列目の２つの値の差をk+1で割ることによって得られます。この結果得られた行列の第１行が
となっています。
離散数学
[
D1] 高橋 巌郎, 藤重 悟, 離散数学, 岩波書店, 1981
算法
[
S1] 野下 浩平, 高岡 忠雄, 町田 元, 基本的算法, 岩波書店, 1983
[
S2] D. E. Knuth(中川 圭介訳), 準数値算法/算術演算, サイエンス社, 1986