Gaussian integer multiplication, division, and greates common divisor.

gi_arithm.py

"""Greatest common divisor for gaussian integers."""

def floor(x):
    return x // 1

def mult_gi(x, y):
    a, b = x
    c, d = y

    return (a*c - b*d, a*d + b*c)

def div_gi(x, y):
    a, b = x
    c, d = y

    r = (a*c + b*d)/(c**2 + d**2)
    s = (b*c - a*d)/(c**2 + d**2)
    return (r, s)

def gcd_gi(x, y):
    global COUNT
    a, b = x
    c, d = y

    r, s = div_gi(x, y)
    p = floor(r)
    q = floor(s)

    theta = (r-p, s-q)
    gamma = mult_gi(theta, y)

    if gamma == (0, 0):
        return y
    else:
        return gcd_gi(y, gamma)

if __name__ == '__main__':
    x = (85, 0)
    y = (1, 13)
    print(gcd_gi(x, y))