4.5.3 ANALYSIS OF EUCLID S ALGORITHM 343 by (5)1 (Net web server)
4.5.3 ANALYSIS OF EUCLID S ALGORITHM 343 by (5)1 _ = . . ,A,) 2, &n–1(&, (16) U Qn(Al,Aa,. . . ,A,) This formula holds also if Euclid s algorithm is applied for u < U, when Al = 0. Furthermore, because of (8), Qn-1(A2, . . . , A,) and Qn(A1, Aa, . . , A,) are rela- tively prime, and the fraction on the right-hand side of (16) is in lowest terms; therefore u=Qn(Al,Aa ,..., A&, 2, = &n-l&, . . . , A&, (17) where d = gcd(u, v). The worst case. We can now apply these observations to determine the behavior of Euclid s algorithm in the worst case, or in other words to give an upper bound on the number of division steps. The worst case occurs when the inputs are consecutive Fibonacci numbers: Theorem F (G. Lamk, 1845). For n 2 1, let u and u be integers with u > w > 0 such that Euclid s algorithm applied to u and v requires exactly n division steps, and such that u is as small as possible satisfying these conditions. Then u = F n+2 and w = F,+l. Proof. By (17), we must have u = Qn(A1,A2,. . . ,A,)d, where Al, A2, . . . , &, and d are positive integers and A, 2 2. Since Qn is a polynomial with nonnegative coefficients, involving all of the variables, the minimum value is achieved only when Al = 1, . . . , A,-1 = 1, A, = 2, d = 1. Putting these values in (17) yields the desired result. 1 (This theorem has the historical claim of being the first practical application of the Fibonacci sequence; since then many other applications of Fibonacci numbers to algorithms and to the study of algorithms have been discovered.) As a consequence of Theorem F we have an important corollary: Corollary L. If 0 2 u, w < N, the number of division steps required when Algorithm 4.5.2A is applied to u and u is at most [log+(& N)] -2. Proof. By Theorem F, the maximum number of steps, n, occurs when u = F, and v = F%+l, where n is as large as possible with F,+l < N. (The first division step in this case merely interchanges u and u when n > 1.) Since F,+, < N, we have @-l/v% < N (see Eq. 1.2.8-15), so n+ 1 < log+(& N). This completes the proof. 1 Note that log+(& N) is approximately 2.078 In N + 1.672 M 4.785 log,, N + 1.672. See exercises 31 and 36 for extensions of Theorem F.