learn Euclidean algorithms

euclidean.py

from typing import Tuple

"""
Euclidean Algorithm

Finds GCD(Greatest Common Divisor) from two integers.
The algorithm is built on the proof that states common divisors of (A,B)
is equal to (B,R) where R is the remainder of A = BQ + R. When R is 0, 
A = BQ, B is the greatest common divisor of (A,B) because A and B is both
multiple of B.
"""
def euclid_gcd(x: int, y: int) -> int:
    x = abs(x)
    y = abs(y)
    a = max(x, y)
    b = min(x, y)
    q = a // b  #just for learning
    r = a % b

    while r > 0:
        a = b
        b = r
        q = a // b 
        r = a % b
    return b

"""
Euclidean Algorithm (recursive)
"""
def euclid_gcd2(x: int, y: int) -> int:
    a = max(x, y)
    b = min(x, y)
    if b > 0:
        return euclid_gcd2(b, a % b)
    else:
        return a

"""
Extended Euclidean Algorithm

Linear Diophantine equation Ax + By = C is soluble if C is multiple of gcd(A,B).
This function returns the particular solution (x,y) of given equation in tuple.
"""
def ext_euclid(A: int, B: int, c: int) -> Tuple[int, int]:

    if A == 0 or B == 0:
        print("solver not implemented")
        return (0,0)

    a = max(A, B)
    b = min(A, B)
    q = a // b
    r = a % b

    if r == 0:
        t = 0
        s = c // b  # when r==0, b is gcd(a,b).
        
        # c must be multiple of gcd, otherwise this linear Diophantine equation
        # is insoluable
        if c/b - s > 0:
            print("cannot solve this equation")
            return (0,0)

        x = t       
        y = s - q*t
        return (x,y)
    else:
        s,t = ext_euclid(b, r, c)
        x = t
        y = s - q*t
        return (x,y)


def check(val, exp):
    if val != exp:
        print(f"check failed")
        print(f"  received: {val}")
        print(f"  expected: {exp}")
    else:
        pass


check(euclid_gcd(1,1), 1)
check(euclid_gcd(1,5), 1)
check(euclid_gcd(2,4), 2)
check(euclid_gcd(7,9), 1)
check(euclid_gcd(3,9), 3)
check(euclid_gcd(11,13), 1)

check(euclid_gcd(-1,-1), 1)
check(euclid_gcd(-2,4), 2)

check(euclid_gcd2(1,1), 1)
check(euclid_gcd2(1,5), 1)
check(euclid_gcd2(2,4), 2)
check(euclid_gcd2(7,9), 1)
check(euclid_gcd2(3,9), 3)
check(euclid_gcd2(11,13), 1)

check((0,0), (0,0))

# 17x+13y=1 --> (x,y)=(-3,4)
check(ext_euclid(17,13,1), (-3,4))

# 10x+4y=30 --> (x,y)=(15,-30)
check(ext_euclid(10,4,30), (15,-30))

# not implemented
check(ext_euclid(0,1,0), (0,0))
check(ext_euclid(1,0,0), (0,0))

#insoluble
check(ext_euclid(2,4,5), (0,0))