Greatest Common Denominator

gcd.py

from tabulate import tabulate


def linear_gcd(a, b):
    table_cols = []

    (a0, s, t) = (a, 1, 0)
    (b0, u, v) = (b, 0, 1)

    remainder = quotient = new_u = new_v = None


    while b0 != 0:
        table_cols.append([a0, b0, remainder, quotient, s, t, u, v, new_u, new_v, s*a + t*b])

        quotient = a0 // b0
        remainder = a0 % b0

        new_u = (s - quotient*u)
        new_v = (t - quotient*v)    

        (a0, s, t) = (b0, u, v)
        (b0, u, v) = (remainder, new_u, new_v)

    table_cols.append([a0, b0, remainder, quotient, s, t, u, v, new_u, new_v, s*a + t*b])

    print(tabulate(table_cols, headers=['a', 'b', 'r', 'q', 's', 't', 'u', 'v', 'new_u', 'new_v', 'sA + tB']))

    return (a0, s, t)



linear_gcd(330, 156)

## Output:
#   a    b    r    q    s    t    u    v    new_u    new_v    sA + tB
# ---  ---  ---  ---  ---  ---  ---  ---  -------  -------  ---------
# 330  156              1    0    0    1                          330
# 156   18   18    2    0    1    1   -2        1       -2        156
#  18   12   12    8    1   -2   -8   17       -8       17         18
#  12    6    6    1   -8   17    9  -19        9      -19         12
#   6    0    0    2    9  -19  -26   55      -26       55          6