322 ARITHMETIC 4.5.2 (Web hosting contract) As an example of Algorithm
322 ARITHMETIC 4.5.2 As an example of Algorithm B, let us consider u = 40902, 21 = 24140, the same numbers we have used to try out Euclid s algorithm. Step Bl sets k t 1, u + 20451, IJ + 12070. Then t is set to -12070, and replaced by -6035; then v is replaced by 6035, and the computation proceeds as follows: U V t 20451 6035 +14416, +7208, +3604, +1802, +901 901 6035 -5134, -2567; 901 2567 -1666, -833; 901 833 +68, +34, +17; 17 833 -816, -408, -204, -102, -51; 17 51 -34, -17; 17 17 0. The answer is 17 . 2l = 34. A few more iterations were necessary here than we needed with Algorithm A, but each iteration was somewhat simpler since no division steps were used. A MIX program for Algorithm B requires just a little more code than for Algorithm A. In order to make such a program fairly typical of a binary computer s representation of Algorithm B, let us assume that MIX is extended to include the following operators: l SLB (shift left AX binary). C = 6; F = 6. The contents of registers A and X are shifted left M binary places; that is, lrAX/ c 12 rAXI modB O where B is the byte size. (As with all MIX shift commands, the signs of rA &nd rX are not affected.) l SRB (shift right AX binary). C = 6; F = 7. The contents of registers A and X are shifted right M binary places; that is, b-Ax c lb~lP J~ l JAE, JAO (jump A even, jump A odd). C = 40; F = 6, 7, respectively. A JMP occurs if rA is even or odd, respectively. l JXE, JXO (jump X even, jump X odd). C = 47; F = 6, 7, respectively. Analogous to JAE, JAO. Program B (Binary gcd algorithm). Assume that u and 21 are single-precision positive integers, stored respectively in locations U and V; this program uses Algorithm B to put gcd(u, v) into rA. Register assignments: t = rA, k = rI1. 01 ABS EQU 1:5 02 Bl ENTI 0 1 Bl. Find Power of 2. 03 LDX U 1 rx +- 21. 04 LDAN V 1 rA + -v. 05 JMP IF 1 06 2H SRB 1 A Halve rA, rX. 07 INCI 1 A kck+l. 08 STX U A u t u/2. 09 STA V(ABS) A v t v/2.