##############################################
# Problem 0 - Euclidean Algorithm
##############################################

def gcd_ea(a,b):
    """
    This function returns the Greatest Common Divisor of a and b.
    """
    x = abs(a)
    y = abs(b)
    while (y != 0): #Can speed things up using y != 0 vs y > 0
        # print (x,y)
        r = mod(x,y) #Is faster faster with x%y
        x = y
        y = r
    return x #Return gcd(a,b)

import time

t = time.time() #Start Time
gcd_ea(8675309,3892394)
dt = time.time() - t #Difference in Time = End Time - Start Time
print dt

t = time.time() #Start Time
gcd_ea(31313,519)
dt = time.time() - t #Difference in Time = End Time - Start Time
print dt

##############################################
# Problem 1.c - Extended Euclidean Algorithm
##############################################

def gcd_eea(a,b):
    u = 1
    g = a
    y = b
    x = 0
    while (y != 0):
        q = g//y #Faster with g//y vs floor(g/y)
        t = g%y #Is faster faster with %
        s = u - q*x
        u = x
        g = y
        x = s
        y = t
    v = (g - a*u)/b
    return (g,u,v)

gcd_eea(31313,519)
gcd_eea(167181,163961)
gcd_eea(8675309,3892394)

import time

t = time.time()
gcd_eea(8675309,3892394)
dt = time.time() - t
dt

##############################################
# Problem 1.d - Extended Euclidean Algorithm
##############################################

def gcd_eea_posu(a,b):
    u = 1
    g = a
    y = b
    x = 0
    while (y != 0):
        q = floor(g/y)
        #q = g//y #Faster with g//y vs floor(g/y)
        t = g%y #Is faster faster with %
        s = u - q*x
        u = x
        g = y
        x = s
        y = t
    v = (g - a*u)/b
    while (u < 0):
        u = u + b/g
        v = v - a/g
    return (g,u,v)

t = time.time()
gcd_eea_posu(8675309,3892394)
dt = time.time() - t
dt

gcd_eea_posu(31313,519)
gcd_eea_posu(167181,163961)
gcd_eea_posu(8675309,3892394)