Question
a. Find gcd(31415, 14142) by applying Euclid’s algorithm.
b. 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).
Answer
a) gcd(31415, 14142) by applying Euclid’s algorithm is sovled below
gcd(31415,14142)
=gcd(14142,3131)
=gcd(3131,1618)
=gcd(1618,1513)
=gcd(1513,105)
=gcd(1513,105)
=gcd(105,43)
=gcd(43,19)
=gcd(19,5)
=gcd(5,4)
=gcd(4,1)
=gcd(1,0)
=1.
Here, total iterations or divisions are 11.. Mod (%) is just an integer division where we return the remainder
b)
The number of divisions madeby Euclid’s algorithm is 11.
The number of divisions madeby the consecutive integer checking algorithm on each of its 14142 iterations is either 1 and 2;
Hence, the total number of multiplications is between1·14142and2·14142.
Therefore,Euclid’salgorithm will be between1·14142/11≈1300and 2·14142/11≈2600times faster.