############################################### Problem 0 - Euclidean Algorithm##############################################
defgcd_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%yx=yy=rreturnx#Return gcd(a,b)
importtime
t=time.time()#Start Timegcd_ea(8675309,3892394)dt=time.time()-t#Difference in Time = End Time - Start Timeprintdt
1
0.000687837600708
t=time.time()#Start Timegcd_ea(31313,519)dt=time.time()-t#Difference in Time = End Time - Start Timeprintdt
173
0.00163507461548
############################################### Problem 1.c - Extended Euclidean Algorithm##############################################
defgcd_eea(a,b):u=1g=ay=bx=0while(y!=0):q=g//y#Faster with g//y vs floor(g/y)t=g%y#Is faster faster with %s=u-q*xu=xg=yx=sy=tv=(g-a*u)/breturn(g,u,v)
############################################### Problem 1.d - Extended Euclidean Algorithm##############################################
defgcd_eea_posu(a,b):u=1g=ay=bx=0while(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*xu=xg=yx=sy=tv=(g-a*u)/bwhile(u<0):u=u+b/gv=v-a/greturn(g,u,v)