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 consecutive integers from min{m, n} down to gcd(m, n).

Answer 1

Answer:

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.

Answer 2

Following are the solution to the given question:

$\to \gcd(31415,14142) \\\\ \to \gcd(14142,3131) \\\\ \to \gcd(3131,1618)\\\\ \to \gcd(1618,1513) \\\\ \to gcd(1513,105) \\\\ \to gcd(105,43) \\\\ \to gcd(43,19) \\\\ \to gcd(19,5) \\\\ \to gcd(5,4) \\\\ \to gcd(4,1) \\\\ \to 1$

Using the Euclidean algorithm:

gcd(a,b): //defining a method gcd that takes two parameters  

  if a<b://defining an if block that checks a less than b  

    return gcd(b,a)//using the return keyword that calls gcd method

elif a%b==0://defining elif block that check remainder value equal to 0  

    return b//returning b value

else://defining else block

     return gcd(b,a%b)//using the return keyword that calls the gcd method

• Since gcd() of the input was 1. Particularly, if we need to go from min(31415,14142) to 1.
• It would require 14142 iterations, while using the Euclidian approach.
• we obtained the solution in 10 steps, indicating that the Euclidian technique is 1414 times faster than that of the brute force algorithm in this situation, as demonstrated by the above solution.

Learn more:

brainly.com/question/10555022