アルゴリズム論特論(塩田)第4回 (1)
   ユークリッドのアルゴリズムの計算量(緩い評価)

ループ回数の評価

 記号は第3回 Alg.6 ( ユークリッドのアルゴリズム ), Alg.9 ( 拡張ユークリッドアルゴリズム ) のとおりとします。 簡単のため、その入力 $a$, $b$ は
$a \gt b \gt 0$
を満たすと仮定し、 剰余 $r_n$ は $r_n \geqq 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)$.
(証明終)

 次のページでは、計算量のオーダーは本当はもっと小さいことを示します。