Euclidean Algorithm

euclidean_algo.py

# coding: utf-8

import sys

def gcd_rec(x, y):
    if x < y:
        x, y = y, x
    rem = x % y
    div = x / y
    if rem == 0:
        return y, {x:0, y:1}
    elif rem == 1:
        return rem, {x:1, y:-div}
    else:
        gcd, d = gcd_rec(y, rem)
        print_equation(d, gcd)

        co_rem = d[rem]
        co_y = d[y]
        assert co_rem * rem + co_y * y == gcd
        co_x = co_rem
        co_y = co_y - co_rem * div

        return gcd, {x:co_x, y:co_y}


def gcd_fac(x, y):
    gcd, d = gcd_rec(x, y)

    print_equation(d, gcd)

    co_x = d[x]
    co_y = d[y]
    neg_x_sign = 1 if co_x <= 0 else -1
    d_pair = {
        x: co_x + y * neg_x_sign,
        y: co_y + x * -neg_x_sign
    }

    print_equation(d_pair, gcd)
    return gcd


def print_equation(coefs, value):
    x, y = coefs.keys()
    print '%d * %d %s %d * %d = %d' % (
        coefs[x], x,
        '+' if coefs[y] >= 0 else '-',
        abs(coefs[y]), y,
        value
    )


def main():
    print 'input two integers:'
    x, y = map(int, sys.stdin.readline().split())
    assert x != y
    print gcd_fac(x, y)


if __name__ == '__main__':
    main()