Question

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.

Answer 1

Answer:

Explanation:

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.