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=50,size=2*10**5):
   """ repeats the following "size" times: Choose two
   random integers, n bits long each (between 1 to 2**n-1).
   Checks if they are relatively prime.
   Computes the frequency and the derived approximatio to pi."""
   
   count=0
   for i in range(0,size):  
      if gcd(random.randint(1,2**n-1),random.randint(1,2**n-1))==1:
         count += 1
   return count/size, (6*size/count)**0.5