Cedant web hosting - 4.5.3 ANALYSIS OF EUCLID S ALGORITHM 357 (1975), 20-281,
4.5.3 ANALYSIS OF EUCLID S ALGORITHM 357 (1975), 20-281, who established that 7, = y Inn + C + O(n-1/6+e), see D. E. Knuth, Computers and Math. with Appiic. 2 (1976), 137-139. Thus the conjecture (48) is fully proved. The average running time for Euclid s algorithm on multiple-precision in- tegers, using classical algorithms for arithmetic, was shown to be of order (I+ log(m=4u, v)lgcd(u, 4)) 1% mink v> by G. E. Collins, in SIAM J. Computing 3 (1974), l-10. Summary. We have found that the worst case of Euclid s algorithm occurs when its inputs u and v are consecutive Fibonacci numbers (Theorem F); the number of division steps when v = n will never exceed r4.8 log,o N -0.321. We have determined the frequency of the values of various partial quotients, showing, for example, that the division step finds [u/v] = 1 about 41 percent of the time (Theorem E). And, finally, the theorems of Heilbronn and Porter prove that the average number T, of division steps when v = n is approximately ((12 In 2)/r ) In n z 1.9405 log,, n, minus a correction term based on the divisors of n as shown in Eq. (53). EXERCISES b 1. [20] Since the quotient [v/vJ is equal to unity over 40 percent of the time in Algorithm 4.5.2A, it may be advantageous on some computers to make a test for this case and to avoid the division when the quotient is unity. Is the following MIX program for Euclid s algorithm more efficient than Program 4.5.2A? LDX u rX+-u. JMP 2F 1H STX V v c rX. SUB v rAtu-vu. CMPA V SFtAx 5 rAX + rA. JL 2F Is u-v < v? DIV V rX c rAXmodv. 2H LDA V rA+v. mz IB Done if rX = 0. m