The Euclidean algorithm has been known for over 2000 years and has always been a favorite among
Question:
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 \(\operatorname{gcd}(A, B)\) with \(A, B \geq 1\).
STEP 1 Set \(A_{1}=A, B_{1}=B, C_{1}=1\)
STEP \(2 n\) (1) If \(A_{n}=B_{n}\) stop. \(\operatorname{gcd}(A, B)=A_{n} C_{n}\)
(2) If \(A_{n}\) and \(B_{n}\) are both even, set \(A_{n+1}=A_{n} / 2, B_{n+1}=B_{n} / 2, C_{n+1}=2 C_{n}\)
(3) If \(A_{n}\) is even and \(B_{n}\) is odd, set \(A_{n+1}=A_{n} / 2, B_{n+1}=B_{n}, C_{n+1}=C_{n}\)
(4) If \(A_{n}\) is odd and \(B_{n}\) is even, set \(A_{n+1}=A_{n}, B_{n+1}=B_{n} / 2, C_{n+1}=C_{n}\)
(5) If \(A_{n}\) and \(B_{n}\) are both odd, set \(A_{n+1}=\left|A_{n}-B_{n}ight|, B_{n+1}=\min \left(B_{n}, A_{n}ight)\), \(C_{n+1}=C_{n}\)
Continue to step \(n+1\).
a. To get a feel for the two algorithms, compute \(\operatorname{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?
Step by Step Answer: