4.5.2 THE GREATEST COMMON DIVISOR 321 Bl. Find (Web site counters)
4.5.2 THE GREATEST COMMON DIVISOR 321 Bl. Find power of 2 B5. Reset max(u, v) Fig. 9. Binary algorithm for the greatest common divisor. A binary method. Since Euclid s patriarchal algorithm has been used for so many centuries, it is a rather surprising fact that it may not always be the best method for finding the greatest common divisor after all. A quite different gcd algorithm, which is primarily suited to binary arithmetic, was discovered by J. Stein in 1961 [see J. Comp. Phys. 1 (1967), 397-4051. This new algorithm requires no division instruction; it relies solely on the operations of(i) subtraction, (ii) testing whether a number is even or odd, and (iii) shifting the binary representation of an even number to the right (halving). The binary gcd algorithm is based on four simple facts about positive integers u and v: a) If u and u are both even, then gcd(u, w) = 2 gcd(u/2, v/2). [See Eq. (8).] b) If u is even and u is odd, then gcd(u, V) = gcd(u/2, v). [See Eq. (6).] c) As in Euclid s algorithm, gcd(u, V) = gcd(u -w, v). [See Eqs. (13), (2).] d) If u and v are both odd, then u -2) is even, and Iu -U[ < max(u, v). These facts immediately suggest the following algorithm: Algorithm B (Binary gcd algorithm). Given positive integers u and U, this algorithm finds their greatest common divisor. Bl. [Find power of 2.1 Set k +- 0, and then repeatedly set k +- k + 1, u + u/2, v t v/2, zero or more times until u and v are not both even. B2. [Initialize.] (Now the original values of u and ZI have been divided by 2 , and at least one of their present values is odd.) If u is odd, set t t --2, and go to B4. Otherwise set t t u. B3. [Halve t.] (At this point, t is even, and nonzero.) Set t + t/2. B4. [Is t even?] If t is even, go back to B3. B5. [Reset max(u, v).] If t > 0, set u t t; otherwise set 21 c -t. (The larger of u and v has been replaced by (t(, except perhaps during the first time this step is performed.) B6. [Subtract.] Set t t u–21. If t # 0, go back to B3. Otherwise the algorithm terminates with us 2 as the output. 1