gcd.py

def display_gcd(x,y):
    """ greatest common divisor of two integers - Euclid's algorithm
        Function prints all intermediate results along the way """
    assert isinstance(x,int) and isinstance(y,int) 
           # type checking: x and y both integers
    x,y=abs(x),abs(y) # simultaneous assignment to x and y
            # gcd invariant to abs. Both x,y now non-negativr
    if x<y:
        x,y=y,x   # switch x and y if x < y. Now y <= x
    print(x,y)
    while y>0:
        x,y=y,x%y
        print(x,y)
    return x


def gcd(x,y):
    """ greatest common divisor of two integers - Euclid's algorithm """
    assert isinstance(x,int) and isinstance(y,int) # type checking: x and y both integers
    x,y=abs(x),abs(y) # simultaneous assignment to x and y
            # gcd invariant to abs. Both x,y now non-negativr
    if x<y:
        x,y=y,x   # switch x and y if x < y. Now y <= x
    while y>0:
        x,y=y,x%y
    return x


def slow_gcd(x,y):
    """ greatest common divisor of two integers - naive inefficient method """
    assert isinstance(x,int) and isinstance(y,int) # type checking: x and y both integers
    x,y=abs(x),abs(y) # simultaneous assignment to x and y
            # gcd invariant to abs. Both x,y now non-negativr
    if x<y:
        x,y=y,x   # switch x and y if x < y. Now y <= x
    for g in range(y, 0, -1): # from x downward to 1
        if x%g == y%g == 0:  # g divides both x and y?
            return g
    return None # should never get here, 1 divides all

import random

def samplegcd(n,iternum):
   """ repeats the following iternum times: Choose two
   random integers, n bits long each (leading zeroes OK).
   Check if they are relatively prime. Compute the frequency"""
   
   count=0
   for i in range(0,iternum):  
      if gcd(random.randint(1,2**n-1),random.randint(1,2**n-1))==1:
         count += 1
   return(count/iternum)