impl/python.py

from .math_gcd_lcm_types import GcdLcm

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 on unbounded integers. Never negative; gcd_wide(0, 0) is 0."""
    x, y = abs(a), abs(b)
    while y != 0:
        x, y = y, x % y
    return x


def gcd(a: int, b: int) -> int:
    _check_safe("a", a)
    _check_safe("b", b)
    return gcd_wide(a, b)


def lcm(a: int, b: int) -> int:
    g = gcd(a, b)
    if g == 0:
        return 0
    # Divide before multiplying: a * b overflows long before the lcm does.
    result = abs(a) // g * abs(b)
    if result > MAX_SAFE:
        raise ValueError("the lcm of %d and %d exceeds 2^53 - 1" % (a, b))
    return result


def gcd_lcm(a: int, b: int) -> GcdLcm:
    """Greatest common divisor and least common multiple of two integers.

    Both are returned together because a caller needing one nearly always
    needs the other (common denominators, repeating schedules).
    """
    return GcdLcm(gcd=gcd(a, b), lcm=lcm(a, b))