2 Karatsuba系列のアルゴリズム

2.1 Karatsuba乗算

$2n$ 桁の数 $u,v$ の乗算を行うことを考える。$u,v$ を基数 $b$ の冪 $x=b^n$ を用いて

$$u=u_1x+u_0,v=v_1x+v_0$$ (2.12)

のように上半分と下半分に分ければ、$x$を基数とした乗算と考えることができる。このとき単純に$w=uv$を求めると、

$$w=u_1v_1x^2+(u_0v_1+u_1v_0)x+u_0v_0$$

のように$n \times n$¹が4回必要である。しかし

$$u_0v_1+u_1v_0=u_1v_1+u_0v_0-(u_1-u_0)(v_1-v_0)$$ (2.13)

という関係を使えば$n \times n$は3回で済むことが分かる。ここでさらに $u_1,u_0,v_1,v_0$の上位の桁を$0$で埋めて桁数を偶数にするか、あるいは始めから$u,v$の桁数を2の冪にしておけば、3回の$n \times n$に同じアルゴリズムを再帰的に適用することができる。この乗算アルゴリズムをKaratsuba乗算(Karatsuba Multiplication)という。

このアルゴリズムで$n \times n$に必要な時間を$T(n)$とする。$n \times n$には $n/2 \times n/2$ が3回と$n/2 \pm n/2$が数回必要であるから、

$$T(n) = 3T(n/2)+cn/2$$

$$= 3^{\lg n}T(1)+cn\left((3/2)^{\lg n}-1\right)$$

$$= n^{\lg 3}(T(1)+c)-cn$$

$$= \Theta(n^{\lg 3}) \qquad (\lg 3 \approx 1.585)$$ (2.14)

となり、$\Theta(n^2)$ よりも少ない時間で乗算が実行できることが分かる。

2.2 Karatsuba除算

$4n$桁の数$u$と$2n$桁の数$v$ $(u<vb^{2n})$の除算を行い、$2n$桁の商$w$と$2n$桁の余り$r$を求めることを考える。$u,v,w,r$を基数$b$の冪$x=b^n$を用いて

$$u=u_3x^3+u_2x^2+u_1x+u_0,v=v_1x+v_0,w=w_1x+w_0$$ (2.15)

のように表せば、$x$を基数とした除算と考えることができる。筆算のアルゴリズムから、$w_1$を求めるためには除算 $(u_3x+u_2)/v_1$を行わなければならないが、これはちょうど$4n \div 2n$の半分の大きさであるから、Karatsuba乗算と同じように桁数を調節することで再帰的に求めることができる。後はこのようにして求めた商と余りを$w_1,r_1'$として、

$$r_1=r_1'x+u_1-v_0w_1$$ (2.16)

とおき、$r_1 \ge 0$となるまで

$$w_1:=w_1-1,r_1:=r_1+v$$ (2.17)

を繰り返せば$w_1$が求まる。この繰り返しを2回以下にするには、筆算のときと同様に$v_1 \ge x/2$となるように、したがって$b$進表示における$v$の最上位の桁が$b/2$以上となるように調節すれば良い。$w_0$についても同様にして求めることができる。$r_1/v_1$の商$w_0$と余り$r_0'$を再帰的に求め、

$$r_0=r_0^{\prime}x+u_0-v_0w_0$$ (2.18)

とおき、$r_0 \ge 0$となるまで $r_0:=r_0+v,w_0:=w_0-1$を繰り返せば良い。ここで求まった$r_0$がそのまま余り$r$となる。この除算アルゴリズムをKaratsuba除算(Karatsuba Division)という。

このアルゴリズムで $2n \div n$ に必要な時間を $T(n)$ とする。$2n \div n$には$n \div n/2$が2回と $n/2 \times n/2$が2回、$n+n$等が数回必要であるから、$n \times n$に必要な時間を$M(n)$として、

$$T(n) = 2T(n/2)+2M(n/2)+cn$$

$$= nT(1)+\sum_{k=1}^{\lg n}2^kM(n/2^k)+cn \lg n$$

$$= \sum_{k=1}^{\lg n}2^kM(n/2^k)+\Theta(n \lg n)$$ (2.19)

となる。具体的に$M(n)=cn^2$とすれば

$$T(n) = \sum_{k=1}^{\lg n}cn^2/2^k+\Theta(n \lg n)$$

$$= cn^2(1-1/n)+\Theta(n \lg n)$$

$$= M(n)+\Theta(n \lg n)$$ (2.20)

となり、 $M(n)=cn^{\lg 3}$とすれば

$$T(n) = \sum_{k=1}^{\lg n}cn^{\lg 3}(2/3)^k+\Theta(n \lg n)$$

$$= 2cn^{\lg 3}(1-n/n^{\lg 3})+\Theta(n \lg n)$$

$$= 2M(n)+\Theta(n \lg n)$$ (2.21)

となる。第4章で述べるアルゴリズムを使えば$M(n)=cn \lg n$となるので、

$$T(n) = \sum_{k=1}^{\lg n}cn\lg (n/2^k)+\Theta(n \lg n)$$

$$= cn \lg^2 n-cn\lg n(1+\lg n)/2+\Theta(n \lg n)$$

$$= (M(n)\lg n)/2 +\Theta(n \lg n)$$ (2.22)

となる。

2.3 Karatsuba開平

$4n$桁の数$u$を開平して$2n$桁の平方根$s$と余り$r$を求めることを考える。$u,s$を基数$b$の冪$x=b^n$を用いて

$$\begin{eqnarray*} u&=&u_3x^3+u_2x^2+u_1x+u_0 \\ s&=&s_1x+s_0 \end{eqnarray*}$$

のように表せば、$x$を基数とした開平と考えることができる。筆算のアルゴリズムより、まず$u_3x+u_2$の平方根と余りを求めなければならないが、これはちょうど$u$の半分のサイズであるから再帰的に求めることができる。このようにして求めた平方根を$s_1$、余りを$r_1$とおく。次に$s_0$を求めるために、 $(r_1x+u_1)/2s_1$の商を$s_0$、余りを$r_0'$、そして $r_0=r_0'x+u_0-s_0^2$とおく。$r_0 \ge 0$となるまで

$$r_0:=r_0+2s_0-1,s_0:=s_0-1$$ (2.23)

を繰り返せば$s_0$が求まる。特に$u_3 \ge b/4$の場合には、1回条件分岐をするだけとなる。この開平アルゴリズムをKaratsuba開平(Karatsuba Square Root)という。

このアルゴリズムで$2n$桁の数を開平するのに必要な時間を$T(n)$とする。$4n$桁の開平には $\mathrm{sqrt}(2n)$ が1回、$2n \div n$ が1回、$n \times n$ が1回、$2n-2n$ が1回、$n+n$等が数回必要である。$2n \div n$に必要な時間を$D(n)$、$n \times n$に必要な時間を$M(n)$とすれば、

$$T(n) = T(n/2)+D(n/2)+M(n/2)+cn/2$$

$$= T(1)+\sum_{k=1}^{\lg n}(D(n/2^k)+M(n/2^k)+cn/2^k)$$

$$= \sum_{k=1}^{\lg n}(D(n/2^k)+M(n/2^k))+\Theta(n)$$ (2.24)

となる。ここでKaratsuba乗除算を使えば

$$T(n) = \sum_{k=1}^{\lg n}(3M(n/2^k)+\Theta(n/2^k \lg (n/2^k)))+\Theta(n)$$

$$= (9M(n/2))/2+\Theta(n \lg n)$$

$$= 3M(n)/2+\Theta(n \lg n)$$ (2.25)

となる。

2.4 Karatsuba基数変換

例えば $3141592$ という $10$ 進表現は、$3,141,592$のように3桁ごとに区切れば $10^3=1000$ 進表現としてみることができる。このように基数を$b$から$b^n$に変換する、あるいはその逆は単に($b$ 進表示における)桁の区切りを変えるだけで良く、隣の桁に対する繰上げや繰り下げが起こることはない。このことを利用したのがここで述べるアルゴリズムである。

$2n_0$桁の$b_0$進自然数$u$を基数変換し、$b_1$進表現を得たいとする。まず $b_0^{n_0} \le b_1^{n_1}$となるような最小の$n_1$を求め、$x=b_1^{n_1}$とする。このとき、$u$の$b_1$進表示は$2n_1$桁以下である。次に$u$の$x$進表示を得るために$u/x$を行い、その商を$q$、余りを$r$とする。そうすると$u$は$x$進表示では$q,r$の2桁で表されることになるが、先に述べたことから$q,r$はそのまま$b_1$進表示における上位$n_1$桁と下位$n_1$桁になっている。後は$q,r$に対して同じアルゴリズムを再帰的に適用すれば$u$の$b_1$進表示が得られる。この基数変換アルゴリズムをKaratsuba基数変換(Karatsuba Radix Conversion)という。実際に必要とされる基数は限られているであろうから、予め$b_1^{2^n}$等を計算しておくとよい。

このアルゴリズムで$b_0$進$n$桁の数を $b_1$進表現に変換するのに必要な時間を$T(n)$とする。$b_1$の冪を予め求めておけば単に除算を繰り返すだけであるから、

$$T(n) = 2T(n/2)+D(n/2)$$

$$= \sum_{k=1}^{\lg n}D(n/2^k)$$ (2.26)

となる。具体的にKaratsuba乗算を用いて $D(n)=2M(n)+\Theta(n \lg n)$とすれば、

$$T(n) = \sum_{k=1}^{\lg n}(2M(n/2^k)+\Theta(n/2^k \lg (n/2^k)))$$

$$= M(n)+\Theta(n \lg n)$$ (2.27)

となる。