Write algorithms that solve the following exercises and analyze their running ti

Question

Write algorithms that solve the following exercises and analyze their running times. You may write actual code or pseudocode for each problem in this part.

Write an alternative gcd algorithm based on the following observations (arrange so that a > b ):

a. gcd (a , b ) = 2gcd (a/ 2, b/ 2) if a and b are both even.

b. gcd (a , b ) = gcd (a/ 2, b ) if a is even and b is odd.

c. gcd (a , b ) = gcd (a , b/ 2) if a is odd and b is even.

d. gcd (a , b ) = gcd ((a + b )/ 2, (a b )/ 2) if a and b are both odd.

Explanation / Answer

Assign the value of min(m,n) to t.

Divide m by t. If the remainder of this division is 0, go to step 3; otherwise, go to step 4.
Divide n by t. If the remainder of this division is 0, return the value of t as the answer and stop; otherwise, go to step 4.
Decrease the value of t by 1. go to step 2

a. gcd(a, b) = 2gcd(a/2, b/2) if a and b are both even

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.