# 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)