impl/python/gcd.py

_MAX_SAFE = 9007199254740991


def _check_safe(name: str, value: int) -> None:
    if isinstance(value, bool) or not isinstance(value, int):
        raise TypeError("%s must be an integer, received %r" % (name, value))
    if value > _MAX_SAFE or value < -_MAX_SAFE:
        # Python would happily go further, but TypeScript cannot, and the three
        # languages must give the same answer or the same error.
        raise ValueError("%s is outside the safe integer range (±9007199254740991)" % (name,))


def gcd_wide(a: int, b: int) -> int:
    """Euclid's algorithm with no range limit. Never negative; gcd_wide(0, 0) is 0.

    Exported for fraction arithmetic (math.rational), which reduces products
    that are already past 2^53 before it checks them.
    """
    x, y = abs(a), abs(b)
    while y != 0:
        x, y = y, x % y
    return x


def gcd(a: int, b: int) -> int:
    """Greatest common divisor, never negative; gcd(0, n) is |n| and gcd(0, 0) is 0."""
    _check_safe("a", a)
    _check_safe("b", b)
    return gcd_wide(a, b)