Geocities web hosting - 4.5.2 THE GREATEST COMMON DIVISOR 331 not on
4.5.2 THE GREATEST COMMON DIVISOR 331 not on the actual values of u and v. Let us call this approximation a lattice-point model, since we will say that we are at the point (m, n) when Llg ~1 = m and [lg v] = n. From point (m, n) the algorithm takes us to (m , n) if u > U, or to (m,n ) if u < U, or terminates if u = v. For example, the calculation starting with u = 20451 and u = 6035 begins at the point (14,12), then goes to (9,12), P!ll), (%9), (4,9), (4,5), (4,4), and terminates. In line with the comments of the preceding paragraph, we will make the following assumptions about the probability that we reach a given point just after point (m, n): Case 1, m > n. Case 2, m < 12. Next point Probability Next point Probability Cm - Ln) % (m,n-1) a (m -2, n) a (m,n-2) a (rn,l) w-1. . h 0) w -1 Case 3, m = n > 0. Next point Probability Cm - 2, n), Cm, n -2) a, a Cm - 3, n), (3 n -3) QJ R (0, ni im, 0) c:,i,~id,m terminate w-1 For example, from points (5,3) the lattice-point model would go to points (4,3), (3,3), (2,3), (1,3), (0,3) with the respective probabilities 4, a, i, &, &; from (4,4) it would go to (2,4), (1,4), (0,4), (4,2), (4, I), (4,0), or would terminate, with the respective probabilities a, A, &, $, 4, &, i. When m and n are both 0, the formulas above do not apply; the algorithm always terminates in such a case, since m = n = 0 implies that u = v = 1. The detailed calculations of exercise 18 show that this lattice-point model is somewhat pessimistic. In fact, when m > 3 the actual probability that Algorithm B goes from (m, m) to one of the two points (m -2, m) or (m, m -2) is equal to i, although we have assumed the value 3; the algorithm actually goes from (m, m) to (m-3, m) or (m, m-3) with probability $, not a; and it actually goes from (m + 1, m) to (m, m) with probability 4, not 4. The probabilities in the model are nearly correct when Irn -n( is large, but when Irn -nl is small the model predicts slower convergence than is actually obtained. In spite of the fact that our model is not a completely faithful representation of Algorithm B, it has one great virtue: It can be completely analyzed! Furthermore, empirical experiments with Algorithm B show that the behavior predicted by the lattice- point model is analogous to the true behavior.