Question

Consider two different versions of algorithm for finding gcd of two numbers (as given below), Estimate how many times faster it will be to find gcd (31415, 14142) by Euclid’s algorithm compared with the algorithm based on checking consecutive integers from min{m, n} down to gcd(m,n). Provide all the steps related to your solution.

Answer 1

Step-by-step explanation:

Step 1:

a) The formula for compute greatest advisor is

gcd(m,n) = gcd (n,m mod n)

the gcd(31415,14142) by applying Euclid's algorithm is

gcd(31,415,14,142) =gcd(14,142,3,131)

=gcd=(3,131, 1,618)

=gcd(1,618, 1,513)

=gcd(1,513, 105)

=gcd(105, 43)

=gcd(43, 19)

=gcd(19, 5)

=gcd(5, 4)

=gcd(4, 1)

=gcd(1, 0)

=1

STEP 2

b) The number of comparison of given input with the algorithm based on checking consecutive integers and Euclid's algorithm is

The number of division using Euclid's algorithm =10 from part (a)

The consecutive integer checking algorithm:

The number of iterations =14,142 and 1 or 2 division of iteration.

14,142 ∠= number of division∠ = 2*14,142

Euclid's algorithm is faster by at least 14,142/10 =1400 times

At most 2*14,142/10 =2800 times.