Ask Question
6 November, 04:03

Consider two different versions of algorithm for finding gcd of two numbers (as given below), 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). Provide all the steps related to your solution.

+2
Answers (1)
  1. 6 November, 04:54
    0
    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.
Know the Answer?