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.