%$OpenXM: OpenXM/doc/compalg/num.tex,v 1.3 2000/10/03 01:44:03 noro Exp $ \chapter{整数} \section{整数の表現} 計算機においては高々レジスタのビット長 (ワード長)の数に対する演算 しか提供されず, それ以上の大きさの整数 ({\bf 多倍長整数} あるいは {\bf bignum}) に対する演算は \begin{enumerate} \item 整数を, ある整数 $B$ により $B$ 進表示する. \item 各桁どうしの演算を CPU の整数演算機能により行なう. \item これらの組合せにより元の整数どうしの演算結果を得る. \end{enumerate} という形で行われる. $B$ の値は, ワード長に近い大きさの 2 ベキとする場 合が多い. これは, \begin{itemize} \item $B$ を大きくすると $B$ 進表現の桁数が少なくで済む \item $B$ 以上の整数の上位, 下位の桁への分解が, ビットシフト演算で済む \end{itemize} という理由による. しかし, $B$ を, 半ワード長より大 きくとる場合, 乗除算において, \begin{enumerate} \item 単精度整数 $\times$ 単精度整数 $\rightarrow$ 倍精度整数 \item 倍精度整数 $\rightarrow$ 単精度整数 $\times$ 単精度整数 + 単精度整数 \end{enumerate} という二つの演算が必要になる. 標準的な C 言語においては上記の演算は通常提供されておらず, アセンブリ 言語によりこれらを記述する必要も生ずる. ただし, 最近広く使用されている {\tt gcc} では{\tt long long} あるいは {\tt unsigned long long} 宣言に より64 bit 整数演算を用いることができ, それにより C 言語のみでこれらの演算 が可能となる. 例えば 1. の演算は \begin{verbatim} typedef unsigned int UL; typedef unsigned long long ULL; UL a,b,ch,cl; ULL c; ... c = (ULL)a*(ULL)b; ch = (UL)(c>>32); cl = (UL)(c&(((ULL)1)<<32)); \end{verbatim} により, {\tt ch}, {\tt cl} に各々 64bit の乗算結果の上位, 下位 32bit が格納される. しかし, {\tt gcc} の CPU 毎の実装の仕方によっては, 32 bit 乗除算が常に関数呼び出しになったりする場合もあるので, 確実な高速化 のためにはやはりアセンブラあるいはインラインアセンブラを使うのも止むを 得ない. 以下, $B$ 進表現された二つの自然数 $$u=u_nB^n+u_{n-1}B^{n-1}+\cdots+u_0$$ $$v=v_mB^m+v_{m-1}B^{m-1}+\cdots+v_0$$ ($0\le u_i, v_j \le B-1$) に対し, 加減乗除演算を行うことを考える. \section{加算} 加算は, 筆算を行うように下位の桁から繰り上がりとともに足していけばよい. しかし, 実際の計算機上での実現はそれほど自明ではない. $B$ として計算機 のワード長一杯 (32bit CPU なら $B=2^{32}$) を選んだ場合, 次のようなア ルゴリズムとなる. \begin{al} \begin{tabbing} \\ Input : $u=\sum_{i=0}^{n-1} u_iB^i$, $v=\sum_{i=0}^{n-1}v_iB^i$\\ Output : $w = u+v$\\ $c \leftarrow 0$\\ for \= $i=0$ to $n-1$\\ \> $t \leftarrow u_i+v_i \bmod B$\\ \> if \= $t < u_i$\\ \>\> $t \leftarrow t+c \bmod B$\\ \>\> $c\leftarrow 1$\\ \> else\\ \>\> $t \leftarrow t+c \bmod B$\\ \>\> if $t < c$ then $c \leftarrow 1$ else $c \leftarrow 0$\\ \> $w_i \leftarrow t$\\ $w_n \leftarrow c$\\ return $\sum_{i=0}^n w_iB^i$ \end{tabbing} \end{al} このアルゴリズムに現れる $c \leftarrow a+b \bmod B$ は, $$a+b \ge B \Rightarrow c \leftarrow a+b-B$$ を意味する. $B$ がワード長一杯 の場合, Section \ref{cpuint} で述べたように加算は $B$ を法として行われ る. これは, C 言語では, \begin{verbatim} unsigned int a,b,c; ... c = a+b; \end{verbatim} により実行できる. 繰り上がりは, $a+b \bmod B$ が $a$ または $b$ より小 さくなっているかどうかで検出できるため, ここで述べたアルゴリズムにより 加算が正しく実行できるのである. \section{減算} 減算も, 筆算と同様の仕方で行う. \begin{al} \begin{tabbing} \\ Input : $u=\sum_{i=0}^{n-1} u_iB^i$, $v=\sum_{i=0}^{n-1}v_iB^i$ ($u\ge v$)\\ Output : $w = u-v$\\ $b \leftarrow 0$\\ for \= $i=0$ to $n-1$\\ \> $t \leftarrow u_i-v_i \bmod B$\\ \> if \= $t > u_i$\\ \>\> $t \leftarrow t-b$\\ \>\> $b\leftarrow 1$\\ \> else\\ \>\> $t \leftarrow t-b \bmod B$\\ (B)\>\> if $t = B-1$ then $b \leftarrow 1$ else $b \leftarrow 0$\\ \> $w_i \leftarrow t$\\ return $\sum_{i=0}^{n-1} w_iB^i$ \end{tabbing} \end{al} このアルゴリズムに現れる $c \leftarrow a-b \bmod B$ は, $$a-b < 0 \Rightarrow c \leftarrow a-b+B$$ を意味する. この操作も, C 言語では \begin{verbatim} unsigned int a,b,c; ... c = a-b; \end{verbatim} により実行される. 繰り下がりは, $a-b \bmod B$ が $a$ より大きいかどうか で検出できる. (B) における $B-1$ との比較は, ここでの繰り下がりが, $t=0$ かつ $b=1$ の場合にのみ生ずるためである. \section{乗算} 乗算も筆算と同様の方法で計算できる. \begin{al} \begin{tabbing} \\ Input : $u=\sum_{i=0}^{n-1} u_iB^i$, $v=\sum_{i=0}^{m-1}v_iB^i$\\ Output : $w = uv$\\ for \= $i=0$ to $n-1$\\ \> $w_i \leftarrow 0$\\ for $j=0$ to $m-1$\\ \>$c \leftarrow 0$\\ \>for \= $i=0$ to $n-1$\\ \>\> $t \leftarrow w_{i+j}+u_iv_j+c$\\ (M)\>\> $t = t_hB+t_l$ ($0 \le t_h, t_l < B$) と分解\\ \>\> $w_{i+j}\leftarrow t_l$\\ \>\> $c\leftarrow t_h$\\ \>$w_{n+j} \leftarrow c$\\ \end{tabbing} \end{al} (M) で計算される $t$ は, $0\le, w_{i+j}, c u_{n+1}B^2+u_n B + u_{n-1} \Rightarrow q \le \hat{q}-1.$ \end{pr} $\hat{q} = q+2$ ならば常に命題 \ref{check} の不等式が成立するから, こ のチェックを高々 2 回行なうことで, $\hat{q} = q$ または $\hat{q}=q+1$ とできる. このチェックを行ったのち, なお $\hat{q} \neq q$ となる 可能性については次の命題が成り立つ. \begin{pr} $\hat{q} > q$ かつ $\hat{q}(v_n B + v_{n-1}) \le u_{n+1}B^2+u_n B + u_{n-1}$ $\Rightarrow u \bmod v \ge (1-2/B)v.$ \end{pr} すなわち, ランダムに $u$, $v$ を選んだとき, $\hat{q} \neq q$ となる 確率は $2/B$ 程度となり, $B=2^{32}$ の場合には極めて小さい確率でしか 起こらないことが分かる. この $\hat{q}$ により, $\hat{r} = u-\hat{q}v$ を実際に計算し て, もし $\hat{r}$ が負ならば $q = \hat{q}-1$ であり, $r = u-qv = \hat{r}+v $ となる. 命題 \ref{check} の不等式は $$\hat{q}v_{n-1} > (u_{n+1}B+u_n-\hat{q}v_n)B+u_{n-1}$$ と書けるから, このチェックで必要 になる整数演算は高々倍精度で十分である. まとめると, \begin{itemize} \item $\hat{q} = q$ または $\hat{q} = q + 1$で, 後者となる確率は極めて小さい. \item 整数乗除算は倍精度乗除算で十分である. \end{itemize} 前者は, 実際に足し戻しが必要になる場合が極めて小さいことを意味し, 除算 の効率向上につながるが, 反面, 足し戻しを行なう部分のバグとりに苦労する ことなる. また, 後者は, 倍精度整数乗除算さえ実現されていれば, このアル ゴリズムは実現可能であることを示している. 上記の方法で, $v_n \ge \lfloor B/2 \rfloor$ なる制限が与えられているが, これは, あらかじめ $u, v$ に $d=\lfloor B/(v_n+1)\rfloor$ を掛けておけば 満たされる. 商は変化せず, 剰余は $d$ で割ればよい. また, $B$ が 2 の冪 の場合には, $d$ と値として 適当な 2 の冪がとれる. この場合, $d$ による 乗除算は, シフト演算となり都合がよい. \section{冪} 整数の冪乗の計算は, 次のような 2 通りのアルゴリズムで行うことができる. \begin{al} \label{ipwr0} \begin{tabbing} \\ Input : $u \in \Z$, $e \in \N$\\ Output : $w = u^e$\\ $(k_mk_{m-1}\cdots k_0)_2 \leftarrow e$ の 2 進表示 ($k_m=1$)\\ $t \leftarrow u$\\ $w \leftarrow 1$\\ for \= $i=0$ to $m$\{\\ (a)\> if ( $k_i=1$ ) then $w = wt$\\ \> if ( $i=m$ ) then return $w$\\ \> $t \leftarrow t^2$\\ \} \end{tabbing} \end{al} \begin{pr} アルゴリズム \ref{ipwr0} は $u^e$ を出力する. \end{pr} \proof (a) において, $t=u^{2^i}$ より, このアルゴリズムは, $k_i=1$ なる $i$ に対する $u^{2^i}$ の積を出力する. この値は $u^e$ に等しい. \qed \begin{al} \label{ipwr1} \begin{tabbing} \\ Input : $u \in \Z$, $e \in \N$\\ Output : $w = u^e$\\ $(k_mk_{m-1}\cdots k_0)_2 \leftarrow e$ の 2 進表示 ($k_m=1$)\\ $w \leftarrow 1$\\ for \= $i=m$ to $0$\{\\ (a)\> $w \leftarrow w^2$\\ \> if ( $k_i=1$ ) then $w = wu$\\ \}\\ return $w$ \end{tabbing} \end{al} \begin{pr} アルゴリズム \ref{ipwr1} は $u^e$ を出力する. \end{pr} \proof $m=0$ の時 $w=u$ となり正しい. $m-1$ まで正しいとする. $e_1 = (k_mk_{m-1}\cdots k_1)$ を $m$ bit 数とみなせば, 帰納法の 仮定により, $i=0$ で (a) において $w=u^{e_1}$. このとき, このアルゴリズムは $w^2\cdot u^{k_0}=u^{2e_1+k_0}$ を出力するが, これは $u^e$ に等しい. \qed\\ これらのアルゴリズムは, $e$ 乗を, それぞれ $\log_2 e$ 回程度の 2 乗算と 乗算で実行できる. このアルゴリズムは, 整数の冪乗に限らず, あらゆる 場合に用いられる汎用的なものである. 前者のアルゴリズムは, \begin{itemize} \item 指数 $e$ の各ビットを右から左にスキャンする. \item 常に掛ける数は同じ. \item 保持すべき途中結果は $w$ のみ. \end{itemize} 後者は \begin{itemize} \item 指数 $e$ の各ビットを左から右にスキャンする. \item 掛ける数が変化していく. \item 保持すべき途中結果は $w$, $t$ の両方. \end{itemize} という特徴を持ち, それぞれ一長一短がある.