Web hosting unlimited bandwidth - 4.5.3 ANALYSIS OF EUCLID S ALGORITHM 353 a) As
4.5.3 ANALYSIS OF EUCLID S ALGORITHM 353 a) As mentioned earlier, the last quotient is always 2 or more. Furthermore, we have the obvious identity /a… , zn-1, zn + 1/ = 1×1, *. * ,2,-l, %, I/, (44 and this shows how partial fractions whose last quotient is unity are related to regular continued fractions. b) The values in the right-hand columns have a simple relationship to the values in the left-hand columns; can the reader see the correspondence before reading any further? The relevant identity is 1 -/zr, X2,. . . 1&J = /&Xl -19×2 ,…, &J; (45) see exercise 9. c) There is symmetry between left and right in the first two columns: If /AI,&… ,A,/ occurs, so does /At,. . . ,A2,Al/. This will always be the case (see exercise 26). d) If we examine all of the quotients in the table, we find that there are 96 in all, of which 8 = 40.6 percent are equal to 1, & = 21.9 percent are equal to 2, & = 8.3 percent are equal to 3; this agrees reasonably well with the probabilities listed above. The number of division steps. Let us now return to our original problem and investigate T,, the average number of division steps when v = n. (See Eq. (19).) Here are some sample values of T,: n= 95 96 97 98 99 100 101 102 103 104 105 Tn = 5.0 4.4 5.3 4.8 4.7 4.6 5.3 4.6 5.3 4.7 4.6 n = 996 997 998 999 1000 1001 ..a 9999 10000 10001 Tn = 6.5 7.3 7.0 6.8 6.4 6.7 ..a 8.6 8.3 9.1 n= 49999 50000 50001 *** 99999 100000 100001 Tn = 10.6 9.7 10.0 *a* 10.7 10.3 11.0 Note the somewhat erratic behavior; T, tends to be higher than its neighbors when n is prime, and it is correspondingly lower when n has many divisors. (In this list, 97, 101, 103, 997, and 49999 are primes; 10001 = 73 . 137, 50001 = 3.7.2381, 99999 = 3.3.41.271, and 100001 = 11.9091.) It is not difficult to understand why this happens: if gcd(u, V) = d, Euclid s algorithm applied to u and v behaves essentially the same as if it were applied to u/d and v/d. Therefore, when v = n has several divisors, there are many choices of u for which n behaves as if it were smaller. Accordingly let us consider another quantity, rn, which is the average num- ber of division steps when 2, = n and when u is relatively prime to n. Thus 7, = –& c T(m, n). (46) O~m