# Benchmarking the greatest common divisor algorithm from math import gcd as lehmer_gcd def gcd(a, b): while b: a, b = b, a%b return a from random import randrange import time, sys if sys.platform == "win32": timer = time.clock else: timer = time.time def time_gcd(a_digits, b_digits, ntrials=100, g_digits = 0): A = 10**a_digits B = 10**b_digits # g_digits used to artificially inflate the gcd C = 10**g_digits test_values = [] for _ in xrange(ntrials): g = randrange(C)+1 test_values.append((randrange(A)*g, randrange(B)*g)) t0 = timer() results1 = [gcd(a, b) for a, b in test_values] t1 = timer() results2 = [lehmer_gcd(a, b) for a, b in test_values] t2 = timer() # double check that both algorithms produced the same results assert results1 == results2 print "%8d %8d %8d %8d %10f %10f %10f" % (a_digits, b_digits, g_digits, ntrials, t2-t1, t1-t0, (t1-t0)/(t2-t1)) print "%8s %8s %8s %8s %10s %10s %10s" % ("a_digits", "b_digits", "g_digits", "ntrials", "C_Lehmer", "Py_Euclid", "Factor") print "%8s %8s %8s %8s %10s %10s %10s" % ("--------", "--------", "--------", "-------", "--------", "---------", "------") # inputs have similar sizes time_gcd(1, 1, 100000) time_gcd(2, 2, 100000) time_gcd(4, 4, 100000) time_gcd(7, 7, 100000) time_gcd(10, 10, 10000) time_gcd(20, 20, 10000) time_gcd(50, 50, 10000) time_gcd(100, 100, 1000) time_gcd(1000, 1000, 1000) time_gcd(10000, 10000, 100) print "\nLopsided gcds\n-------------" time_gcd(20, 100) time_gcd(100, 20) time_gcd(1000, 3) time_gcd(3, 1000) time_gcd(10000, 1) time_gcd(1, 10000) time_gcd(500, 400) time_gcd(400, 500) print "\nLarge gcd\n---------" time_gcd(10, 10, 1000, g_digits=10) time_gcd(20, 20, 1000, g_digits=20) time_gcd(100, 100, 1000, g_digits=100)