320 ARITHMETIC 4.5.2 (Unable to start debugging on the web server) textbooks. Euclid also gave a
320 ARITHMETIC 4.5.2 textbooks. Euclid also gave a method (Proposition 34) to find the least common multiple of two integers u and w, namely to divide u by gcd(u, V) and to multiply the result by V; this is equivalent to Eq. (10). If we avoid Euclid s bias against the numbers 0 and 1, we can reformulate Algorithm E in the following way. Algorithm A (Modern Euclidean rtlgorithm). Given nonnegative integers u and V, this algorithm finds their greatest common divisor. (Note: The greatest common divisor of arbitrary integers u and 21 may be obtained by applying this algorithm to 1~1) and 1~11, because of Eqs. (2) and (3).) Al. [w = O?] If v = 0, the algorithm terminates with ZL as the answer. A2. [Take umodv.] Set r + umodv, u + V, w t T, and return to Al. (The operations of this step decrease the value of 21, but they leave gcd(u,v) unchanged.) 1 For example, we may calculate gcd(40902,24140) as follows: gcd(40902,24140) = gcd(24140,16762) = gcd(16762,7378) = gcd(7378,2006) = gcd(2006,1360) = gcd(1360,646) = gcd(646,68) = gcd(68,34) = gcd(34,O) = 34. A proof that Algorithm A is valid follows readily from Eq. (4) and the fact that gcd(u, v) = gcd(w, u - qw), (13) if 4 is any integer. Equation (13) holds because any common divisor of u and w is a divisor of both w and u - qw, and, conversely, any common divisor of w and u - qw must divide both u and w. The following MIX program illustrates the fact that Algorithm A can easily be implemented on a computer: Program A (Euclid s dgorithm). Assume that u and w are single-precision, nonnegative integers, stored respectively in locations U and V; this program puts gcd(u, w) into rA. LDX U 1 rx t 21. JMP 2F 1 IH STX V T v + rx. SRAX5 T rAX + rA. DIV V T rX t rAXmodv. 2H LDA V 1 +T rA+ v. JXNZ 1B 1-t T Done if rX = 0. 1 The running time for this program is 19T + 6 cycles, where T is the number of divisions performed. The discussion in Section 4.5.3 shows that we may take T = 0.842766 In N + 0.06 as an approximate average value, when 21 and w are independently and uniformly distributed in the range 1 5 u, w 5 N.