6.6 The Euclidean Algorithm 103the lemma above gives the bound
log 2 Fk+log 2 Fk+1≈log 2
√^1
5
(
1+
√
5
2
)k
+log 2
√^1
5
(
1+
√
5
2
)k+1
=−log 2 5+(2k+ 1) log 2(
1+
√
5
2
)
≈ 1. 388 k− 1. 628 ,so we have overestimated the number of steps only by a factor of about
1.388, or less than 40%.
Fibonacci numbers are not only good for giving examples of large num-
bers for which we can see how the Euclidean Algorithm works; they are
also useful in obtaining an even better bound on the number of steps. We
state the result as an exercise. Its content is that, in a sense, the Euclidean
Algorithm is longest on two consecutive Fibonacci numbers.
6.6.10Suppose thata<band the Euclidean Algorithm applied toaandb
takesksteps. Prove thata≥Fkandb≥Fk+1.
6.6.11Consider the following version of the Euclidean Algorithm to compute
gcd(a, b): (1) Swap the numbers if necessary to havea≤b; (2) ifa= 0, then
returnb; (3) ifa = 0, then replacebbyb−aand go to (1).
(a) Carry out this algorithm to compute gcd(19,2).
(b) Show that the modified Euclidean Algorithm always terminates with the
right answer.
(c) How long does this algorithm take, in the worst case, when applied to two
100-digit integers?6.6.12Consider the following version of the Euclidean Algorithm to compute
gcd(a, b). Start with computing the largest power of 2 dividing bothaandb.If
this is 2r, then divideaandbby 2r. After this “preprocessing,” do the following:
(1) Swap the numbers if necessary to havea≤b.
(2) Ifa = 0, then check the parities ofaandb;ifais even, andbis odd, then
replaceabya/2; if bothaandbare odd, then replacebbyb−a; in each
case, go to (1).
(3) ifa= 0, then return 2rbas the g.c.d.Now come the exercises:
(a) Carry out this algorithm to compute gcd(19,2).
(b) It seems that in step (2), we ignored the case where bothaandbare even.
Show that this never occurs.
(c) Show that the modified Euclidean Algorithm always terminates with the
right answer.