Question

Estimate how many times faster it will be to find gcd(31415, 14142) by the Euclid’s algorithm compared with the algorithm based on checking consecutive integers from min{m, n} down to gcd(m, n).

hint: to compare the performance, you may count the number of divisions each algorithm takes.

(math and formulas to be done using Latex math symbols)

Answer 1

Answer

Euclid algorithm solution works based on the replacement of larger number with its difference with smaller number.

For given numbers

Total number of divisions by Euclid algorithm = 11

Now, Consecutive integer checking algorithm can do either 1 or 2 divisions per iteration and number of iterations would be 14142 (minimum number).

So total number of divisions can be between 14142 and 28284.

Based on this Euclid algorithm will be between 4142/11 ≈ 1300 and 28284/11 ≈ 2600 times faster.