アルゴリズム論特論（塩田）第4回 (1)
ユークリッドのアルゴリズムの計算量（緩い評価）
ループ回数の評価
記号は第3回（ 5月10日 ）
Alg.6 ( ユークリッドのアルゴリズム ),
Alg.9 ( 拡張ユークリッドアルゴリズム ) のとおりとします。
簡単のため、その入力 $a$, $b$ は
$a \gt b \gt 0$
を満たすと仮定します。
Lemma 1 $r_{n+2} \lt \frac{1}{2}r_n$.
大雑把に言うと、数列 $\{\,r_{n}\,\}$ は公比 $\frac{1}{\sqrt{2}}$ の等比数列以上の速さで減少してゆく、
という意味です。
証明 (i) $r_{n} \lt 2 \times r_{n+1}$ のとき：
$r_{n}$ を $r_{n+1}$ で割った商は $1$ になるので、余り $r_{n+2}$ は
$r_{n+2} = r_n - 1 \times r_{n+1} \lt r_n - \frac{1}{2} r_n = \frac{1}{2} r_n$
を満たします。
(ii) $r_{n} \geqq 2 \times r_{n+1}$ のとき：
$\{\,r_{n}\,\}$ は減少列ですから $r_{n+2} \lt r_{n+1} \leqq \frac{1}{2} r_n$.
(証明終)
Rem.2 負の余りも使うときは、もっと強く $r_{n+1} \leqq \frac{1}{2} r_n$
が成り立ちます。
Lemma 3 ユークリッドのアルゴリズムのループ回数は $O(\log a)$.
証明
L'a 1 より $r_n$ は番号 $n$ が 2 増えるとビット長が 1 つ以上減ります。
従って、$r_0=a$ のビット長を $k$ とすると、
$n \leqq 2k$ の範囲でアルゴリズムの終了条件 $r_{n+1}=0$ が満たされ、
ループ回数 $\leqq 2 k = O(\log a)$.
(証明終)
緩い評価
Th.4 ( 緩い評価 ) ユークリッドのアルゴリズムの計算量は $O(\log^3 a)$.
証明
$\{\,r_n\,\}$ は減少列ゆえ、全ての $n$ について $r_n \leqq a$ が成り立ちます。
1回のループで用いる計算は $a$ 以下の整数の除算1回だけなので、
計算量 $=$ ループ回数 $\times$ ( 除算の計算量 ) = $O(\log a) \times O(\log^2 a) = O(\log^3 a)$.
(証明終)
本当はもっと計算量は少なくて、