6.6 The Euclidean Algorithm 101- Else (ifa= 0), returnbas the g.c.d. and halt.
When you carry out the algorithm, especially by hand, there is no reason
to interchangeaandbifa<b: we can simply divide the larger number
by the smaller (with remainder), and replace the larger number by the
remainder if the remainder is not 0. Let us do some examples.
gcd(300,18) = gcd(12,18) = gcd(12,6) = 6.
gcd(101,100) = gcd(1,100) = 1.
gcd(89,55) = gcd(34,55) = gcd(34,21) = gcd(13,21) = gcd(13,8)
= gcd(5,8) = gcd(5,3) = gcd(2,3) = gcd(2,1) = 1.You can check in each case (using the prime factorization of the numbers)
that the result is indeed the g.c.d.
If we describe an algorithm, the first thing to worry about is whether it
terminates at all. So why is the Euclidean Algorithm finite? This is easy:
The numbers never increase, one of them decreases whenever step 2 is
executed, and the remain nonnegative; so the whole procedure cannot last
infinitely long.
Then, of course, we have to make sure that our algorithm yields what we
need. This is clear: Step 1 (interchanging the numbers) trivially does not
change the greatest common divisor; step 3 (replacing the larger number by
the remainder of a division) does not change the greatest common divisor
by Exercise 6.6.2(b). And when we halt at step 2, the number returned is
indeed the greatest common divisor of the two current numbers by Exercise
6.6.1.
A third, and more subtle, question you should ask when designing an
algorithm: How long does it take? How many steps will it make before
it terminates? We can get a bound from the argument that proves finite
termination: Since one or the other number decreases any time the loop
of steps 1 and 2 is executed, it will certainly halt in fewer thana+b
iterations. This is really not a great time bound: If we apply the Euclidean
Algorithm to two numbers with 100 digits, then this bound ofa+bsays
that it will not last longer than 2· 10100 steps, which is an astronomical
number, and therefore useless. But luckily this is only an upper bound, and
a most pessimistic one at that; the examples we considered seem to show
that the algorithm terminates much faster than this.
But the examples also suggest that this question is quite delicate. We see
that the Euclidean Algorithm may be quite different in length, depending
on the numbers in question. Some of the possible observations made from
these examples are contained in the following exercises.
6.6.8Show that the Euclidean Algorithm can terminate in two steps for arbi-
trarily large positive integers, even if their g.c.d. is 1.