数理解析研究所講究録 1295 巻 2002 年 80-86

80

大整数に対する整数・有理数変換について
佐々木建昭 (Tateaki Sasaki) ’

筑波大学数学系
INSTITUTE OF MATHEMATICS, UNIVERSITY OF TSUKUBA

高橋善徳 (Yoshinori Takahashi) \dag er

筑波大学教育研究科
MASTER’S PROGRAM 1N EDUCATION, UNIVERSITY OF TSUKUBA

杉本卓也 (Takuya Sugimoto)$\mathrm{I}$筑波大学理工学研究科
MASTER’S PROGRAM

1$1\mathrm{N}$SCIENCE AND ENGINEERING, UNIVERSITY OF TSUKUBA

はじめに
$M$

と $S$ は与えられた整数で、 $M>|S|>0$ を満たすとする。 $M$ と $S$ に対して
$DS\equiv N$$(\mathrm{m}\mathrm{o}\mathrm{d} M)$,$0<D<\sqrt{M}/2,0<|N|<\sqrt{M}/2$,を満たす整数 $D$ と $N$ が存在するとき、 $S$ は $M$ を法として有理数 $N/D$ に等しいとし、

(1)
$S$

から $D,$ $N$ へのが小さいと $D$ と $N$ が存在しないこともあるが、 $M$ が十分
変換を整数・有理数変換という [5] [6]
大きければ大抵存在する)。
整数・有理数変換は数式処理において基本的かつ重要な演算である。 たとえば、計算代数における最も重要な算法である Gr\"obner 基底計算法は、 そのまま実行すると猛烈な中間係数膨張を 51 き起こすことがほとんどで、結果として膨大な計算時間を必要とする。 しかし、 1 語長程度の多数の素数を選び、 それらの素数を法として計算を行えば計算の大部分の過程で中間係数膨張は現れず、 計算は非常に効率化される [3]。 ただし、個々の素数での計算を中国剰余定理でまとめると通常、 巨大な整数が現れ、最後の段階で巨大な整数$[2]_{\text{。}}(M$を有理数に変換する必要がある。計算が大規模になればなるほど、計算時間に占める整数・有理数変換の割合が大きくなるので、 整数・有理数変換を効率化することは実際面で非常に重要である。

整数・有理数変換は通常、 拡張互除法で行われる。整数 GCD(最大公約数) の計算が今でも互除法で行われているように、 この方法は古典的にもかかわらず極めて有効である。 しかしながら、 整数 GCD に対して、 Binary 法や Lehmer 法が考案され ([1] 参照)、 拡張互除法に対しても Sch\"onhage の分割征服法が考案されたように [4]、 整数・有理数変換の効率化も追求すべきである。 Lehmer 法はそのまま拡張互除法にも使える。 Sch\"onhage の分割征服法は、 互いに素な 2 整数 $A,$ $B$ に対し $UA+VB=1$ を満たす整数 $U,$ $V$ を
asaki@math tsukuba.ac$.\mathrm{j}\mathrm{p}$\dagger suunistus00@a01.c0m

kugimoto@math tsukuba.ac$.\mathrm{j}\mathrm{p}$

XII-I

81
計算するものであり、 $2m$ 桁の二つの整数の土位約半分の $m$ 桁を “消去” する操作を再帰的に実行する。

–

方、 2 で見るように整数・有理数変換では $M$ と $S$ の上位桁の約半分を消去するので、 分割征服法がぴった
り当てはまると言える。

本稿は、整数・有理数変換の効率化が Lehmer 法と分割征服法により、 どの程度達成されるかを実際的に調べる。 なお、 本稿では紙面が限られているため Lehemer 法の説明は割愛する (文献 [1] に分かりやすい説

明がある)。

2

拡張互除法と整数・有理数変換
もしも$N/D\equiv S(\mathrm{m}\mathrm{o}\mathrm{d} M)$

かつ $S>0$ ならば一 $N/D\equiv-S$$N/D\equiv(S-M)\equiv-(M-S)(\mathrm{m}\mathrm{o}\mathrm{d} M)$であり、 もしも $S\geq M/2$ ならば$(\mathrm{m}\mathrm{o}\mathrm{d} M)$である。 したがって、以下では一般性を失うことなく、 $S$ は次式を満たすとする。

$M/2>S>0$ .

(2)(1) を満たす整数は (もしあれば) 有名な拡張互除法で計算できる。 So $=M,$$(S_{0}, S_{1}, S_{2}, \cdots, S_{n})$$S_{1}=S$とおき、 剰余列と余因子列 $(C_{0}, C_{1}, C_{2}, \cdots, C_{n}),$ $(D_{0}, D_{1}, D_{2}, \cdots, D_{n})$ を次の算法で計算する (拡張互除法) :$Q_{:}:=\mathrm{q}\mathrm{u}\mathrm{o}$( $S:-1$ , Si),

$i=1\Rightarrow 2\Rightarrow\cdots\Rightarrow n-1$

$S_{:+1}:=S_{i-1}-Q:S_{\dot{l}}$,),(i.e.,$S_{:+1}=\mathrm{r}\mathrm{e}\mathrm{m}(S_{1-1}.,$

with$C\mathit{0}:=1$

and $C_{1}:=0$ ,with$D_{\mathrm{O}}:=0$

and $D_{1}:=1$ .

$S:)$

(3)

$\{$

$C_{\dot{\iota}+1}:=C_{i-1}-Q_{i}C:$,$D_{:+1}:=D_{*-1}.-Q_{i}D_{i}$ここで quo と$\mathrm{r}\mathrm{e}\mathrm{m}$,はそれぞれ quotient と remainder を表す。 このとき次式が成立する。
$C_{:}M+D_{:}S=S_{i}$条件 (2) のため各剰余$S_{j}$$(i=1,2, \ldots, n)$.

(4)は正である。 $(S_{1}, S_{2}, \cdots, S_{n})$ は降下列で $(|D_{1}|, |D_{2}|, \cdots, |D_{n}|)$ は上昇列である。

したがって、 剰余列を計算していき、 $s_{n}<\sqrt{M}/2$ かつ $|D_{n}|<\sqrt{M}/2$ になったならば、 $D=|D_{n}|$ かつ$N=\mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}(D_{n})$$i\geq 2$$S_{n}$のとき、ある。 この条件が満たされなければ、 求める $D$ と $N$ は存在しない。

$S_{i}$とCi,は次の各式を満たす。

$D_{:}$$S_{i}>0$,sign $(D_{i})=(-1)^{:+1}$ ,sign $(C_{\dot{l}})=(-1)^{i}$ ,$|C_{1}.|<|D_{1}.|$,$|C_{i}|<|C_{i\dagger 1}|$,$|C_{i}|<|C_{i+1}|$

with exceptions $C_{2}\leq|D_{2}|$ ,$S_{0}=|D:|S_{\dot{l}}-1+|D_{i-1}|S_{\dot{*}}$,$C_{2}\leq|C_{3}|$(6),$\Rightarrow$$|D:|<S_{0}/S_{i-1}$,$\Rightarrow$$|C_{i}|<S_{1}/S_{i-1}$

.

$\{$

:

$S_{1}=|C_{i}|S:-1+|C_{i-1}|S$

3

(5)

(7)

拡張互除法に対する分割征服法

剰余列計算は二つの整数を組み合わせて最上位桁から順に “消去” していく算法であり、 Lehmer の方法も基本的にそうである。 巨大な整数の GCD 計算では GCD 自体も大きいことが多く、上位桁から順に消去であることが多く、 の上位桁の約するのは実際的である。 一方、 整数・有理数変換では$\mathrm{g}\mathrm{c}\mathrm{d}(M, S)<<S$$S$

半分を消去すれば十分である。 そのことを考慮すれば効率的な算法を構成できる。本節では分割征服に基づくアイデアを述べる。
XII-2

82
整数

$S$

あるいは

は底を $B$ として次のように$B=10^{8}$$k$桁で表現されているとする (通常の計算機では大整数は、 $B=2^{24}$などとして、 そのように表現される)。

$S=s_{k}B^{k}+s_{k-1}B^{k-1}+\cdots+s_{1}B+s_{0}$ ,さて、 $U$ と$V$$(i=k, \ldots, 1,0)$$B>s_{i}\geq 0$

は $U>V\gg 1$ を満たす巨大な整数で、 $M$ と$S$から生成される剰余列の.

(8)$\mathrm{f}\underline{\mathrm{f}\mathrm{l}/\mathrm{f}\mathrm{f}\mathrm{i}^{\neq}\langle}$

$2$

要素で

あるとし、 次のように表現されているとする (um\neq 0)。
$U=u_{m}B^{m}+u_{m-1}B^{m-1}+\cdots+u_{1}B+u0$ ,$B>u:\geq 0$$(i=m, \ldots, 1,0)$,$V=v_{m}B^{m}+v_{m-1}B^{m-1}+\cdots+v_{1}B+v_{0}$ ,$B>v_{i}\geq 0$$(i=m, \ldots, 1,0)$.

(9)

まず、 $U$ と $V$ を次のように上位 $m-m’$ 桁と下位 $m’$ 桁に分割する。
$U=U’B^{m’}+U’’$ ,$U’=u_{m}B^{m-m’}+\cdots+u_{m’}$ ,$U”=u_{m’-1}B^{m’-1}+\cdots+u0$ ,$V=V’B^{m’}+V’’$ ,$V’=v_{m}B^{m-m’}+\cdots+v_{m’}$ ,$V”=v_{m’-1}B^{m’-1}+\cdots+v\mathit{0}$

つぎに、 $U$ と

.

(10)

の上位約 $m/2$ 桁の消去を三つのステップに分けて実行する。

$V$

Step 1:
Step 2:
Step 3:$m’\simeq m/2$とし、 $U’$ との上位約 $m/4$ 桁を消去する、$V’$

その消去結果と $U”,$ $V”$ から約 $3m/4$ 桁の整数
$m’\simeq m/4$とし、と$\tilde{U}$$\tilde{U},\overline{V}$をつくる、の上位約 $m/4$ 桁を消去する。

$\tilde{V}$

Step 1 で $U’$ と $V’$ の上位約 $m/4$ 桁を消去するならば、剰余列の相続く 2 要素として、約 $m/4$ 桁の次なる整数$\hat{U}’$と$\hat{V}’$が得られる。

,$\hat{U}’=c_{u}’U’+d_{u}’V’$

整数$c_{u}’,d_{u}’,$ $c_{v}’,d_{v}’$このとき$\tilde{U}$と$\tilde{V}$

さて、 Step 3 で$2$は約 $m/4$ 桁である。 Step 2 では、$d_{u}’’,$$c_{v}’’,$ $d_{v}’’$

と

.

(11)

を次式で計算する。

$\tilde{V}$

”,

$=$

$\hat{U}’B^{m’}+c_{u}’U’’+d_{u}’V$$\tilde{V}=c_{v}’U+d_{v}’V$$=$$\hat{V}’B^{m’}+d_{v}U’’+d_{v}’V’’$

(12)

.

は約 $3m/4$ 桁 (以下) となるので、 Step 2 の主張は正しい。
$\hat{U}’’$と$\hat{V}’’$の上位約 $m/2$ 桁を取り出して上位約 $m/4$ 桁を消去すれば、剰余列の$\hat{U},\hat{V}$は約 $m/4$ 桁である。

$\hat{U}$と$\hat{V}$,$\hat{V}=c_{v}’’\tilde{U}+d_{v}’’\tilde{V}$

.

(13)

を $U$ と $V$ で表すと次のようになる。

$\hat{U}=\hat{c}_{u}U+\hat{d}_{u}V$,$\hat{c}_{u}=d_{u}’d_{u}+d_{u}’’c_{v}’$,$\hat{d}_{u}=c_{u}’’d_{u}’+d_{u}’’ d_{v}’$,,$\hat{c}_{v}=c_{v}’’d_{u}+d_{v}’’d_{v}$,$\hat{d}_{v}=d_{v}’d_{u}’+d_{v}’’d_{v}’$.

$\hat{V}=\hat{c}_{v}U+\hat{d}_{v}V$$\mathrm{f}\underline{\mathrm{f}\mathrm{l}/\mathrm{f}\mathrm{i}^{\neq}\langle}$が得られる。

$\hat{U}=d_{u}’\tilde{U}+d_{u}’’\tilde{V}$$c_{u}’’,$$\tilde{U}$$=d_{v}U’+d_{v}’V’$$\tilde{U}=c_{u}’U+d_{u}’V$

要素として、約 $m/2$ 桁の次なる整数

整数$\hat{V},$(14)

初期設定を $U=M,$ $V=S$ とすれば、 桁の整数 $M$ との上位約 $k/2$ 桁の消去が、 $k/2$ 桁の整数の上位約 $k/4$ 桁の二つの消去に帰着されるので、 この消去手順を再帰的に適用することにより、 問題が分割
$S$

$k$

征服されることになる。

XII-3

83
4

方法の詳細と正しさの証明,(4) のように表され、 余因子は商列$Q_{n-1})$ のみから計算される。したがって、前節で述べた算法で検討すべきは次の 2 点である。第 1 点: $U\gg V$
剰余列の各要素$s_{i}$

は余因子$c_{i}$と$D_{i}$

で$(Q_{1},$ $Q_{2},$$\cdots$

を上位桁と下位桁へ分割する方法、 第 2 点: $U’,$ $V’$ から計算される商列が $U,$ から計算される商列と等しくなるための条件。第一点は、 $v_{m}\neq 0$ であれば問題はなく、 $V$ の上位の桁のいくっがが 0の場合が問題となる。 そこで、 計算は次の二つの場合、 正常な場合と非正常な場合、 に分けて行われる。
のとき $U$ と

$V$

$V$

正常な場合 :( $U’$ の桁数)$\simeq$( $V’$ の桁数) $\gg 1$ の場合。

この場合は前節で述べた分割征服の方針どおりに分割 (10) を行い、 消去を実行する。

2 整数 $U_{0}=U,$ $U_{1}=V$ から生成される剰余列を(, qヮ-l,$(U_{0}, U_{1}, \cdots, U_{\nu-1}, U_{\nu}, U_{\nu+1})$) とする。 また、 $U_{0}’=U’,$ $U_{1}’=V’$ から生成される剰余列をとし、付随する商タリを (, q9)、余因子タリを$q_{1},$$\cdots$$q_{\nu}$$q_{1}’,$$\cdots,$$(U_{0}’, U\mathrm{i}, \cdots, U_{\nu-1}’, U_{\nu}’, U_{\nu+1}’)$$(c_{0}’, c_{1}’, \cdots, d_{\nu-1}, c_{\nu}’, c_{\nu+1}’),$$q_{\nu-1}’$とする。実際に生成されるのは後者の列であって、$U_{0},$$U_{1}$とし、 付随する商列を$(d_{0}’, d_{1}’, \cdots, d_{\nu-1}’, d_{\nu}’,d_{\nu+1}’)$からは生成されないことに注意されたい。 商列は、対応する要素同士を比べると、最初の方は等しいが、 ある段階から異なってくるはずである。 そこで、 次のようになる条件を求める。

$(q_{1}, q_{2}, \cdots)$と$(q_{1}’, q_{2}’, \cdots)$$q:=q_{i}’$$(i=1, \cdots, \nu-1)$,$q_{\nu}\neq q_{\nu}’$

.

(15)

以下では、 $U$ と $V$ を (10) の $U’,$ $V’$ を用いて次のように表す。
$U=(U’+\epsilon_{u})\mathrm{x}B^{m’}$

実際のプログラムでは$\epsilon_{u}$と$\Xi_{v}$,$V=(V’+\epsilon_{v})\mathrm{x}B^{m’}$,$1>\epsilon_{u},\epsilon_{v}\geq 0$

.

(16)

は’ $=(u_{m’-1}+1)/B,$ $\epsilon_{v}=(v_{m’-1}+1)/B$ と計算する。

命題 1
剰余列

$(U_{0}’, U_{1}’, \cdots, U_{\nu-1}’, U_{\nu}’, U_{\nu+1}’)$

for $j<\nu$ :と対応する商列および余因子列に$-(c_{j+1}’\epsilon_{u}+d_{j+1}’\epsilon_{v})\leq U_{j+1}’<U_{j}’-(d_{j+1}.-d_{j})\epsilon_{u}-(d_{j+1}’-d_{j}’)\epsilon_{v}$or$-(d_{\nu+1}\epsilon_{u}+d_{\nu+1}’\epsilon_{v})>U_{\nu+1}’$$U_{\nu+1}’\geq U_{\nu}’-(d_{\nu+1}-c_{\nu}’)\epsilon_{u}-(d_{\nu+1}’-d_{\nu}’)\epsilon_{v}$

,

.

(17)

が成立すれば、 (15) が成立する。
証明 $i=1,$ $\ldots,j-1$ の場合に $q:=q_{i}’$ を仮定し、 $i=j$ の場合を考える。 仮定より、$\mathrm{c}’\dot{.}U’+d_{\dot{\iota}}’V’=U_{i}’$,$c_{*}’.U+d_{i}’V=U_{\dot{l}}$$\langle i=1,2,$ $\ldots,j)$である。 したがって、 $U_{j+1}$ は次のように表すことができる。
$U_{j+1}$$=$$\mathrm{r}\mathrm{e}\mathrm{m}(Uj-1, U_{j})=(c_{j-1}’-q_{j}c_{j}’)U+(d_{j-1}’-qjd_{j}’)V$$=$$[(c_{j-1}’-q_{j}c_{j}’)(U’+\epsilon_{u})+(d_{j-1}’-q_{j}d_{j}’)(V’+\epsilon_{v})]\mathrm{x}B^{m’}$$=$$[U_{j-1}’-q_{j}U_{j}’+(c_{j-1}’-q_{j}c_{j}’)\epsilon_{u}+(d_{j-1}’-q_{j}d_{j}’)\epsilon_{v}]\mathrm{x}B^{m’}$$=$$[U_{j-1}’-q_{j}’U_{j}’+(c_{j-1}’-q_{j}’c_{j}’)\epsilon_{u}+(d_{j-1}’-q_{j}’d_{j}’)\epsilon_{v}]\mathrm{x}B^{m’}$$+(q_{j}’-q_{j})(U_{j}’+d_{j}\epsilon_{u}+d_{j}’\epsilon_{v})\mathrm{x}B^{m’}$

ここで.

$U_{j-1}’-q_{j}’U_{j}’=U_{j+1}’$.

であり、 また $U_{j}’+c_{j}’\epsilon_{u}+d_{j}’\epsilon_{v}=c_{j}’(U’+\epsilon_{u})+d_{j}’(V’+\epsilon_{v})=(c_{j}’U+d_{j}’V)/B^{m’}$なので、 上式の最後の行は $(q_{j}’-q_{j})U_{j}$ に等しい。
XII-4

84
もしも $q_{j}=q_{j}’$ ならば、

$0\leq \mathrm{r}\mathrm{e}\mathrm{m}(U_{j-1}, U_{j})<U_{j}$0
同様に、 もしも$q_{j}\neq q_{j}’$より次式が成立しなければならない。

.

(18)

$\leq U_{j+1}’+c_{j+1}’\epsilon_{u}+d_{j+1}’\epsilon_{v}<U_{j}’+c_{j}\epsilon_{u}+d_{j}\epsilon_{v}$ならば次式が成立しなければならない。

if$q_{j}>q_{j}’$:$U_{j+1}’+c_{j+1}’\epsilon_{u}+d_{j+1}’\epsilon_{v}\geq U_{j}’+c_{j}’\epsilon_{u}+d_{j}’\epsilon_{v}$if$q_{j}<q_{j}’$:$U_{j+1}’+c_{j+1}’\epsilon_{u}+d_{j+1}’\epsilon_{v}<0$,.

これらは (18) の条件下では成立しないので、 $q_{j}=q_{j}’$ となるには条件 (18) で十分である。 $j<\nu$ では (18)が成立し $j=\nu$ では成立しないことより、 (17) を得る。

1

非正常な場合 : $V’$ の桁数が $U’$ の桁数よりかなり小さい場合。
この場合、 前節に述べた分割では $V’$ の精度が不足して、商が正確に計算できないことがある。 このような非正常な場合には、 $V’$ の桁数を大きくとって ( $m’$ の値を小さくして) 一度だけ剰余を計算する。 こうす
ることにより、 多くの場合、剰余列は正常に戻るが、 戻らなければ再び非正常処理をすればよい。

命題 2

次式を満たすように $m’$ を決めれば、$\mathrm{q}\mathrm{u}\mathrm{o}(U, V)=\mathrm{q}\mathrm{u}\mathrm{o}(U’, V’)$

となる。

.

(19)

$\mathrm{q}\mathrm{u}\mathrm{o}(U’, V’)\epsilon_{v}\leq \mathrm{r}\mathrm{e}\mathrm{m}(U’, V’)<V’+\mathrm{q}\mathrm{u}\mathrm{o}(U’, V’)\epsilon_{v}-1$

証明$q=\mathrm{q}\mathrm{u}\mathrm{o}(U, V),$$q’=\mathrm{q}\mathrm{u}\mathrm{o}(U’, V’)$とおき、 $U$ と $V$ を次のように表す。

$U=(U’+\epsilon_{u})\mathrm{x}B^{m’}$,$V=(V’+\epsilon_{v})\mathrm{x}B^{m’}$,$1>\epsilon_{u},\epsilon_{v}\geq 0$

.

(20)

このとき、 $\mathrm{r}\mathrm{e}\mathrm{m}(U, V)=U-qV=[(U’-qV’)+\epsilon_{u}-q\epsilon_{v}]B^{m’}=[(U’-q’V’)+\epsilon_{u}-q’\epsilon_{v}+(q’-q)(V’+\epsilon_{v})]B^{m’}$であり、 $U’-q’ V’=\mathrm{r}\mathrm{e}\mathrm{m}(U’, V’)$ である。

もしも $q=q’$ ならば、

$0\leq \mathrm{r}\mathrm{e}\mathrm{m}(U, V)<V$

より次式が成立しなければならない。

$0\leq \mathrm{r}\mathrm{e}\mathrm{m}(U’, V’)+\epsilon_{u}-q’\epsilon_{v}<V’+\epsilon_{v}$

.

(21)

同様に、 もしも $q\neq q’$ ならば次式が成立しなければならない。

,

if $q>q’$ :$\mathrm{r}\mathrm{e}\mathrm{m}(U’, V’)+\epsilon_{u}-q’\epsilon_{v}\geq V’+\epsilon_{v}$

if $q<q’$ :$\mathrm{r}\mathrm{e}\mathrm{m}(U’, V’)+\epsilon_{u}-q’\epsilon_{v}<0$.

これらは (21) の条件下では成立せず、 条件 (21) l ま (19) で満たされる。

桁と桁の大きな整数の乗算の計算量を $M(m_{1},m_{2})$ とする。簡単のため剰余列は常に正常であると仮定して、分割征服法の計算量 $T(k)$ を求めよう。 Step I の計算量はStep 垣の計算量は $4M(k/4, k/2)_{\text{、}}$$m_{1}$$m_{2}$$T(k/2)_{\text{、}}$

Step 3 では (14) も計算されるので計算量は $T(k/2)+4M(k/4,3k/4)+8M(k/4, k/4)$ となり、次の漸化式
を得る.

$T(k)=2T(k/2)+4M(k/4, k/2)+8M(k/4, k/4)+4M(k/4,3k/4)$ .

(22)

上式の右辺で $M(k/4,3k/4)\leq 3/2M(k/4, k/2)\leq 3M(k/4, k/4)$ を使って簡単化する。
$T(k) \leq 2^{\log_{2}k}T(1)+7\int_{1}^{\log_{2}k}2^{x+1}M(k/2^{x+1}, k/2^{x+1})dx$

たとえば、 Karatsuba の算法では $M(m, m)\approx 9m^{1.59}$ であるから、 $T(k)\approx 45k^{1.59}$ を得る。 一方、 拡張互除法を効率化した Lehmer 法の計算量は $2.5k^{2}$ なので、分割征服法は巨大整数に対して Lehmer 法より有効なはずである。
XII-5

85
5

計算機への実装と実験

整数や有理数に関する演算は最も基本的なものなので、 アルゴリズムの実装はシステムの一番下のレベ
ルまで立ち入って、 アセンブリ語でプログラムすべきである。 しかしながら、上述のアルゴリズムについて
は、 有効性をテストしている段階なので、 我々は次のようにインプリメンテーションを行い、 実験した。

1. Big-integer の内部表現を Lisp のリストでシミュレートする。
2. すべてのプログラムを Lisp で書く。

3. 底

$B$

としては $B=10^{8}$ あるいは $B=2^{24}$ とする。

表は Euclid 法と Lehmer 法および分割征服法を上記のようにプログラムし、性能を比較したものである。

データはランダムに生成した異なる 10 個のサンプルに対する平均である。

の値が比較的小さくても Lehmer 法は効率的であることが分かる。同時に、 が大きくなっても Lehmer
法は Euclid 法に比べて一定倍しか速くないことも分かる。 このことは、 Euclid 法に比べて Lehmer 法は「巨大整数
小整数」の計算回数が約 $1/10\sim 1/15$ であることから、 当然のことである。 Lehmer 法と分割征
$k$

$k$

$\mathrm{x}$の値が比較的小さくても分割征服法が効率的であり、 桁数が増加するにつれてその効率が向上するという結果を得た。分割を再帰的に行っているので、扱うデータ量が小分けされてキャッシュメ
服法については、$k$

モリに十分収まることも高効率に寄与していると考えられる。
実験環境$\mathrm{O}\mathrm{S}$: Linux 2217 (Vine Linux)、 総メモリ :実験結果 ( $U,$ $V$ それぞれ
–

100
200
300
400
500
600
700
800
900
1000

$k$

桁

$(1\mathrm{O}\mathrm{O}\leq k\leq 1\mathrm{O}\mathrm{O}\mathrm{O})$

Euclid
0.896

3.41
7.66
13.5
21.1

30.0
40.8
53.5
67.3
83.2

Lehmer

0.212
0.778
1.70
2.98
4.62
6.64
8.99
11.7
14.8
18.2

$320\mathrm{M}\mathrm{B}_{\text{、}}$

CPU :Pentium.

$\mathrm{I}\mathrm{I}300\mathrm{M}\mathrm{H}\mathrm{z}$の整数について上位約 $k/2$ 桁を消去)$fi_{\mathrm{p}}^{\backslash }\rfloor\{\mathrm{i}\mathrm{E}\mathrm{I}\mathrm{R}$0.0530
0.129
0.220
0.332
0.465
0.595
0.773
0.927
1.12

1.34

Euclid
0.778
2.94
6.56
11.6
17.6
26.0
35.3
46.0
58.5
71.7

Lehmer$k$$\mathrm{Q}\rfloor$$\#\mathrm{B}$

0.213
0.783
1.71
3.01
4.65
6.69
9.02
11.8

0.0540
0.124
0.21
0.311
0.438
0.561
0.724
0.863

14.9
18.3

1.04
1.26

参考文献
[1] D. E. Knuth: The Art of Coputer Prograrnming, Vol. 2(Seminumerical Algorithm). 1969, Section 4.5.
[2] T. Sasaki and M. Sasaki: On Integer-tO-Rational Conversion Algorithm. SIGASAM Bulletin, Vol. 26,
ACM, 1992, pp. 19-21.
[3] T. Sasaki and T.Takeshima: AModular Method for Gr\"obner-basis Computation over
System of Algebraic Equation. J. Inf. Proces., Vol. 12, 1989, PP. 371-379.

$\mathrm{Q}$and Solving[4] A. Sch\"onhage: Schnelle Berechnung von Kettenbruchentwicklungen. Acta Informatica 1, 1971,$\mathrm{p}\mathrm{p}$.

139-144.
[5] P. S. Wang: A -adic Algorithm for Univariate Partial Fractions. Proc. ACM Symp. on Symbolic andAlgebraic Computation, 1981, PP. 212-217.
$P$

XII-6

86
, M. J. T. Guy and J. H.
[6] P. S.
Bulletin, Vol. 16, ACM, 1982, pp. 2-3.
$\ovalbox{\tt\small REJECT} \mathrm{W}\mathrm{X}\mathrm{a}\mathrm{n}\mathrm{g}$$\mathrm{D}\mathrm{a}\mathrm{v}\mathrm{e}\mathrm{m}\mathrm{p}\mathrm{o}\mathrm{r}\mathrm{t}\ovalbox{\tt\small REJECT} P$-adic Reconstruction of Rational Numbers. SIGSAM

XII-7