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!)'