Ask Question
26 June, 00:02

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).

+4
Answers (1)
  1. 26 June, 01:38
    0
    Euclid's algorithm is at least 14142 / 10 = 1400 times faster than the Consecutive integer checking method.

    On the other hand, Euclid's algorithm is at most 28284 / 10 = 2800 times faster than the Consecutive integer checking method.

    Explanation:

    Formula for calculating GCD (Greatest Common Divisor) is

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

    Calculating the GCD by applying the Euclid's algorithm:

    gcd (31415, 14142) = gcd (14142, 3131)

    gcd (3131, 1618)

    gcd (1618, 1513)

    gcd (1513, 105)

    gcd (105, 43)

    gcd (43, 19)

    gcd (19, 5)

    gcd (5, 4)

    gcd (4, 1)

    gcd (1, 0) = 1

    If we count the above steps, then the number of divisions using Euclid's algorithm = 10

    While the Consecutive integer checking will take 14142 iterations but will take 14142 * 2 = 28284 divisions.

    Euclid's algorithm is at least 14142 / 10 = 1400 times faster than the Consecutive integer checking method.

    On the other hand, Euclid's algorithm is at most 28284 / 10 = 2800 times faster than the Consecutive integer checking method.
Know the Answer?
Not Sure About the Answer?
Get an answer to your question ✅ “Estimate how many times faster it will be to find gcd (31415, 14142) by Euclid's algorithm compared with the algorithm based on checking ...” in 📙 Computers & Technology if there is no answer or all answers are wrong, use a search bar and try to find the answer among similar questions.
Search for Other Answers