4.17 The Euclidean algorithm has been known for over 2000 years and has always been a favorite among number theorists. After these many years, there is now a potential competitor, invented by J. Stein in 1961. Stein's algorithms is as follows. Determine gcd(A, B) with A, B Ú 1. STEP 1 Set A1 = A, B1 = B, C1 = 1 STEP 2 n (1) If An = Bn stop. gcd(A, B) = AnCn (2) If An and Bn are both even, set An+1 = An/2, Bn+1 = Bn/2, Cn+1 = 2Cn (3) If An is even and Bn is odd, set An+1 = An/2, Bn+1 = Bn, Cn+1 = Cn (4) If An is odd and Bn is even, set An+1 = An, Bn+1 = Bn/2, Cn+1 = Cn (5) If An and Bn are both odd, set An+1 = | An - Bn |, Bn+1 = min (Bn, An), Cn+1 = Cn Continue to step n + 1. a. To get a feel for the two algorithms, compute gcd(2152, 764) using both the Euclidean and Stein's algorithm. b. What is the apparent advantage of Stein's algorithm over the Euclidean algorithm? | |
| View Solution | |
| << Back | Next >> |