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?

Fantastic news! We've Found the answer you've been seeking!

Step by Step Answer:

Related Book For  book-img-for-question
Question Posted: