gcd.py

#! /usr/bin/env python

"""
Conceptual complexity: the incidental complexity of the code is low,
because it directly realises the mathematical algorithm, whose intrinsic
complexity is, for the non-mathematical layman, about a cup of tea's
worth of scribbling on a notepad

Time complexity: you know, i have no idea; it's probably related to the
number of factors in the inputs, and the number of factors in common

Space complexity: same as time complexity, because the algorithm is
straightforwardly recursive, unless Python gained the ability to
optimise tail recursion while i wasn't looking
"""

def gcd(a, b):
	"Return the greatest common divisor of a pair of finite integers, calculated using Euler's method"
	if (b > a): a, b = b, a   # make life easier for ourselves
	if (b == 0): return a     # detect the base case
	return gcd(a % b, b)      # recurse with a simplified version of the problem

import sys
if len(sys.argv) > 1:
	print gcd(*map(int, sys.argv[1:]))
else:
	print gcd(0, 0), "is undefined, but comes out as", 0
	print gcd(0, 1), "is undefined, but comes out as", 1
	print gcd(1, 1), "should be", 1
	print gcd(1, 2), "should be", 1
	print gcd(3, 5), "should be", 1
	print gcd(5, 5), "should be", 5
	print gcd(3, 6), "should be", 3
	print gcd(6, 3), "should be", 3
	print gcd(30, 42), "should be", 6
	print gcd(2, 2**16 + 1), "should be", 1