Answer:
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.
