Lab 2: Euclidean algorithm (chapter 3)

In this lab, we will explore Euclid’s algorithm for finding the greatest common divisor of two numbers. You will investigate questions such as how efficient is this algorithm? How many steps does it take to complete? How often does the gcd of two numbers turn out to be exactly 7? or 8? How often are two numbers relatively prime?

Due dates

A draft of your first section, together with the start of your second section, is due Monday, September 30. A final draft is due Monday, October 7.

Code hints

Here is a version of the program Euclid1 which performs the Euclidean algorithm on inputs a,b and shows every step.

def euclid ( a, b ):
    a, b = max(a,b), min(a,b)
    while true:
        quotient = floor(a/b)
        remainder = a - b * quotient
        print '{0} = {1}({2}) + {3}' .format(a,b,quotient,remainder)
        if remainder == 0:
            print "the gcd is", b
            return
        a = b
        b = remainder

For question 2, you will need a version of this program which counts the number of steps. Write a new version of this function called euclid_count which doesn’t print anything at all, but instead returns the number of steps that the algorithm used.

Now, we want to investigate how often does the Euclidean Algorithm require 1 step? 2 steps? 3 steps? and so on. The function euclid3 chooses a random pair (<N) and asks how many steps it took on that pair. It does this over and over again M many times. Try plotting the output!

def euclid3 ( N, M ):
    output = [[i,0] for i in range(20)]
    for i in range(M):
        a = randint(1,N)
        b = randint(1,N)
        count = euclid_count(a,b)
        if count < 20:
            output[count][1] += 1
    return output

For question 3, you will need to modify this program so that it counts how many times each gcd occurs (instead of how many times each step-count occurs)! Create a program called euclid4 which counts how many times each gcd occurs (again up to 20). Plot the output!

Hint: to just get the gcd of two numbers (and not all the printed stuff that comes out of the Euclidean algorithm), you can use the built-in command gcd.

Diophantine equations

If you have time to look at the last question on Diophantine equations, you will need Euclid5, below:

def euclid5(a,b):
    a, b = max(a,b), min(a,b)
    iterates = []
    while b>0:
        q, r = floor(a/b), a % b
        iterates.append( (a,b,q,r) )
        a, b = b, r
    for (a,b,q,r) in iterates:
        print '{0:4d} = {1}({2}) + {3}' .format(a,b,q,r)
    print "so..."
    iterates.pop()
    (a,b,q,r) = iterates.pop()
    x, y = 1, -q
    print '{0:4d} = {1}({2}) + {3}({4})   (now substitute the {3})' .format(r,a,x,b,y)
    while iterates:
        (a,b,q,r) = iterates.pop()
        x, y = y, x-y*q
        print '     = {0}({1}) + {2}({3})' .format(a,x,b,y),
        if iterates:
            print  '  (now substitute the {0})' .format(b)
        else:
            print '  (all done!)'