Euclidの互除法
Abstract
Euclidの互除法を利用することで, 与えられた正整数$ a, bの最大公約数$ \gcd(a, b)が$ O(\log \min(a, b))timeで求まる.
Explanation
Euclidの互除法 (Euclid's algorithm) は, 与えられた正整数$ a, bの最大公約数$ \gcd(a, b)を求めるアルゴリズム. 以下の定理がEuclidの互除法の正当性の根拠になっている.
Theorem (Euclidの互除法)
正整数$ a, b \in \mathbb{Z}_{>0} ~ (a > b)に対して, $ a = qb + r ~ (0 \le r < b)であるとする.
このとき, $ a, bの最大公約数$ \gcd (a, b)について
$ \gcd (a, b) = \gcd (b, r)
が成立する.
Proof
$ g = \gcd (a, b)とすると, $ a', b'を互いに素な正整数として, $ a', b'が互いに素$ \Leftrightarrow$ \gcd(a', b') = 1
$ a = a'g, ~ b = b'g
と表せる. このとき,
$ r = (a' - qb')g
であり, $ a' - qb', b'は互いに素なので, $ \gcd (b, r) = g. $ \blacksquare
Algorithm (Euclidの互除法)
Input:
正整数$ a, b
Output:
正整数$ a, bの最大公約数$ \gcd(a, b)
1. $ b > 0である間, 以下の更新を繰り返す:
$ a, b \gets b, a \mathbin{\mathrm{mod}} b
2. $ aを出力する.
Laméの定理により, Euclidの互除法の計算量を評価できる.
Theorem (Lamé)
正整数$ k \in \mathbb{Z}_{>0}に対し, $ k番目のFibonacci数を$ F_kと書く.
正整数$ a, b \in \mathbb{Z}_{>0}に対して, $ a > b かつ $ b < F_{k+1}ならば,
Euclidの互除法の手順1の繰り返し回数は$ k回未満である.
Proof
TODO 示す.
Implementation
Input
正整数$ a, b
Output
正整数$ a, bの最大公約数$ \gcd(a, b)
Time complexity
$ O(\log \min(a, b))time.
code:python
def gcd(a, b):
while b: a, b = b, a % b
return a
Verification
正しい.
References
T. Cormen, C. Leiserson, R. Rivest, and C. Stein, 『アルゴリズムイントロダクション 第3版』, 近代科学社, 2009.