Recursive implementation of Euclid's algorithm to compute GCD of two integers

euclid_algorithm.py

from typing import Tuple


def gcd(a: int, b: int) -> int:
    """
    Simple recursive implementation of Euclidean algorithm
    """
    a, b = abs(a), abs(b)
    if b == 0:
        return a
    return gcd(b, a % b)


def pulverizer(a: int, b: int) -> Tuple[int]:
    """
    Implementation of the Pulverizer (extended Euclidean algorithm) that gives
    the coefficients of minimum linear combination of `a` and `b`

    Explanation: https://brilliant.org/wiki/extended-euclidean-algorithm/#extended-euclidean-algorithm
    """
    s, s_old, t, t_old = 0, 1, 1, 0
    r, r_old = abs(b), abs(a)
    while r != 0:
        q, r, r_old = r_old // r, r_old % r, r
        s, s_old = s_old - q * s, s
        t, t_old = t_old - q * t, t
    return r_old, s_old, t_old


def main(nums: tuple):
    a, b = nums[0], nums[1]
    # print(f"GCD of {a}, {b}: {gcd(a, b)}")
    results = pulverizer(a, b)
    print(f"GCD: {results[0]} = {results[1]}({a}) + {results[2]}({b})")


if __name__ == "__main__":
    test_cases = [
        (100, 10),
        (6, 5),
        (1680, 640),
        (640, 1680),
        (237, 3),
        (91, 2),
        (12, 0),
        (0, 10),
    ]
    for test in test_cases:
        main(test)