Euclidian Algorithm

euclidian.py

import sys

# Example usage
# $ python euclidian.py 1745 1485
# gcd(1745, 1485) = (1 + 297n) * 1745 - (0 + 349n) * 1485 = 5
# The euclidian algorithm took 6 steps

a = int(sys.argv[1]) # 1745
b = int(sys.argv[2]) # 1485

# Euclidian algorithm with extras
# returns (u, v, d, l)
# where u * a + 
def gcd(a, b):
	if a < b:
		return gcd(b, a)

	r = a % b
	q = a // b

	if r == 0:
		# 0 * a + 1 * b = b
		return (0, 1, b, 1)

	# u * b + v * r = d
	(u, v, d, l) = gcd(b, r)
	
	return (v, u - q * v, d, l + 1)

(u, v, d, l) = gcd(a, b)
#      gcd( a,  b) = (u + b/d n) * a - (v + a/d n) * b =  d
print("gcd(%d, %d) = (%d + %dn) * %d - (%d + %dn) * %d = %d" % (a, b, u, b / d, a, -v, a / d, b, d))
print("The euclidian algorithm took %d steps" % l)