The greatest common divisor (GCD) of two integers
$a$ and $b$ is defined
to be the largest integer that divides both $a$
and $b$ with no remainder. For example, the GCD
of 16 and 28 is 4. In chapter
[2], when we investigate how to
implement rational-number arithmetic, we will need to be able to compute
GCDs in order to reduce rational numbers to lowest terms. (To reduce a
rational number to lowest terms, we must divide both the numerator and the
denominator by their GCD. For example, 16/28 reduces to 4/7.) One way to
find the GCD of two integers is to factor them and search for common
factors, but there is a famous algorithm that is much more efficient.
2つの整数 $a$ と $b$ の最大公約数（GCD）は、$a$ と $b$ の両方を余りなく割り切る最大の整数として定義されます。たとえば、16 と 28 の GCD は 4 です。chapter
[2]で有理数の算術の実装を調べるとき、有理数を既約分数にするために GCD を計算できる必要があります。（有理数を既約分数にするには、分子と分母の両方をその GCD で割らなければなりません。たとえば、16/28 は 4/7 に約分されます。）2つの整数の GCD を見つける1つの方法は、因数分解して共通因子を探すことですが、はるかに効率的な有名なアルゴリズムがあります。
The idea of the algorithm is based on the observation that, if
$r$ is the remainder when
$a$ is divided by
$b$, then the common divisors of
$a$ and $b$ are
precisely the same as the common divisors of $b$
and $r$. Thus, we can use the equation
このアルゴリズムのアイデアは、$a$ を $b$ で割った余りを $r$ とすると、$a$ と $b$ の公約数は $b$ と $r$ の公約数とまったく同じであるという観察に基づいています。したがって、等式
\[\begin{array}{lll}
\textrm{GCD} (a, b) &=& \textrm{GCD}(b, r)
\end{array}\]
to successively reduce the problem of computing a GCD to the problem of
computing the GCD of smaller and smaller pairs of integers. For example,
を使って、GCD の計算問題をより小さな整数のペアの GCD の計算問題に逐次的に帰着できます。たとえば、
\[\begin{array}{lll}
\textrm{GCD}(206,40) & = & \textrm{GCD}(40,6) \\
& = & \textrm{GCD}(6,4) \\
& = & \textrm{GCD}(4,2) \\
& = & \textrm{GCD}(2,0) \\
& = & 2
\end{array}\]
reduces $\textrm{GCD}(206, 40)$ to
$\textrm{GCD}(2, 0)$, which is 2. It is
possible to show that starting with any two positive integers and
performing repeated reductions will always eventually produce a pair
where the second number is 0. Then the GCD is the other
number in the pair. This method for computing the GCD is
known as Euclid's Algorithm.
は $\textrm{GCD}(206, 40)$ を $\textrm{GCD}(2, 0)$（すなわち 2）に帰着します。任意の 2 つの正の整数から始めて繰り返し帰着を行うと、必ず最終的に 2 番目の数が 0 であるペアが得られることを示すことができます。そのとき、GCD はペアのもう一方の数です。GCD を計算するこの方法はユークリッドの互除法として知られています。
It is easy to express Euclid's Algorithm as a
function:
ユークリッドの互除法は容易に関数として表現できます。
function gcd(a, b) {
return b === 0 ? a : gcd(b, a % b);
}
This generates an iterative process, whose number of steps grows as
the logarithm of the numbers involved.
これは反復的プロセスを生成し、そのステップ数は関係する数の対数として増加します。
We can use this theorem to get an order-of-growth estimate for Euclid's
Algorithm. Let $n$ be the smaller of the two
inputs to the
function.
If the process takes $k$ steps, then we must have
$n\geq {\textrm{Fib}} (k)\approx\phi^k/\sqrt{5}$.
Therefore the number of steps $k$ grows as the
logarithm (to the base $\phi$) of
$n$. Hence, the order of growth is
$\Theta(\log n)$.
この定理を使って、ユークリッドの互除法の増加のオーダーの見積もりを得ることができます。$n$ を関数への 2 つの入力のうち小さい方とします。プロセスが $k$ ステップかかるなら、$n\geq {\textrm{Fib}} (k)\approx\phi^k/\sqrt{5}$ でなければなりません。したがって、ステップ数 $k$ は $n$ の（底 $\phi$ の）対数として増加します。よって、増加のオーダーは $\Theta(\log n)$ です。