Question

A. Find gcd(213486, 5423) by applying Euclid’s algorithm. B. Estimate approximately how many times faster it will be to find gcd (213486, 5423) with the help of the Euclid's algorithm compared with the alroithm based on checking consecutive integers from min {m,n} down to gcd(m,n). You may only count the number of modulus divisions of the largest integer by different divisors.

Answer #1

**(A)** .The gcd(213486, 5423) by applying Euclid’s
algorithm:

**(B)**. Lets compare the number of divisions the
algorithms performs on the given input.

There are 8 divisions carried out by Euclid’s algorithm to find the gcd.

If we count the number of divisions required by the consecutive integer checking algorithm for 1 to 17; and after that 5423/17 = 319 consecutive integers. hence the total number of multiplications is 319.

Therefore, Euclid’s algorithm will be = 319 / 8 = 39.875 ≈ 40 times faster than by integer divisions.

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 6 minutes ago

asked 9 minutes ago

asked 17 minutes ago

asked 18 minutes ago

asked 22 minutes ago

asked 25 minutes ago

asked 25 minutes ago

asked 28 minutes ago

asked 44 minutes ago

asked 45 minutes ago

asked 50 minutes ago

asked 50 minutes ago