Extended Euclidean Algorithm extended_gcs(a, b) - With benchmarks.

extended_gcd.py

'''
Extended Euclidean Algorithm extended_gcd(a, b) methods found online.
'''
from functools import wraps
from time import time
 
 
def benchmark(iterations=10000):
    def wrapper(function):
        @wraps(function)
        def func(*args, **kwargs):
            t1 = time()
            for i in range(iterations):
                call = function(*args, **kwargs)
            t2 = time()
            t3 = int(1 / ((t2 - t1) / iterations))
            print func.func_name, 'at', iterations, 'iterations:', t2 - t1
            print func.func_name, 'can perform', t3, 'calls per second.'
            return call
        return func
    return wrapper


'''
The first method I across at
http://rosettacode.org/wiki/Modular_inverse
'''
@benchmark(1000000)
def extended_gcd1(a, b):
    l, r = abs(a), abs(b)
    x, lastx, y, lasty = 0, 1, 1, 0
    
    while r:
        l, (q, r) = r, divmod(l, r)
        x, lastx = lastx - q * x, x
        y, lasty = lasty - q * y, y
    return l, lastx * (-1 if a < 0 else 1), lasty * (-1 if b < 0 else 1)

'''
extended_gcd(3, 26) -> (1, 9, -1)

extended_gcd1 at 1000000 iterations: 5.95399999619
extended_gcd1 can perform 167954 calls per second.
'''


'''
The second method I came across at
https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm#Modular_inverse
'''
@benchmark(1000000)
def extended_gcd2(a, b):
    x, y, u, v = 0, 1, 1 ,0
    while a != 0:
        q, r = b // a, b % a
        m, n = x - u * q, y - v * q
        b, a, x, y, u, v = a, r, u, v, m, n
    return b, x, y
    
'''
extended_gcd2(a, b) -> (1, 9, -1)

extended_gcd2 at 1000000 iterations: 4.02600002289
extended_gcd2 can perform 248385 calls per second.
'''


'''
The last method I came across at
http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm (taken from pseudo code provided)
'''
@benchmark(1000000)
def extended_gcd3(a, b):
    r, old_r = b, a
    x, old_x = 0, 1
    y, old_y = 1, 0
    while r:
        q = old_r // r
        old_r, r = r, (old_r - q * r)
        old_x, x = x, (old_x - q * x)
        old_y, y = y, (old_y - q * y)
    return old_r, old_x, old_y

'''
extended_gcd3(2, 26) -> (1, 9, -1)

extended_gcd3 at 1000000 iterations: 3.875
extended_gcd3 can perform 258064 calls per second.
'''