math.gcd-lcm

def gcd_lcm(a: int, b: int) -> GcdLcm

@dataclass(frozen=True)
class GcdLcm:
    """Both answers together; each is never negative."""

    #: greatest common divisor; gcd(0, 0) is 0
    gcd: int
    #: least common multiple; 0 when either input is 0
    lcm: int

from fune.math.gcd_lcm import gcd_lcm  # math.gcd-lcm@^1

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))

Install

fune build

With that line in your source, in a Python project (language python in fune.project), fune build resolves it and nothing else, pins them in fune.lock, downloads only the Python package of each, and builds the code above into your project’s .fune/build, one readable file per capability with a header linking back here. Or pin a range in fune.project and build in one step:

fune add math.gcd-lcm

The manifest, vectors and README with only the Python implementation. Install it without the registry with fune add ./math.gcd-lcm-1.0.0-python.fune, or fetch it from a terminal with fune pull math.gcd-lcm@1.0.0:python.

The whole function, every language, is one file too: math.gcd-lcm-1.0.0.fune, 10,259 bytes, sha256 c9e41636d824c974f9a85f3a786451805447acfbe1af4ee8a0b3e2d4f96448b9. It installs into a project of any language.

# fune: before math.gcd-lcm

# fune: after math.gcd-lcm

# fune: step math.gcd-lcm after <n|label>

More from the author

The lcm is computed as `|a| / gcd * |b|`, dividing first. The textbook `a * b / gcd` overflows a 64-bit integer, and loses digits in a JavaScript number, long before the answer itself is large; one of the vectors is a case where it does.

Inputs and results are limited to ±(2^53 - 1), the range where a JavaScript number is still an exact integer, so the three languages agree on every answer. An input outside it, or an lcm beyond it, is an error.

Also exported, for capabilities that build on this one: `gcd(a, b)`, `lcm(a, b)`, and `gcdWide`, a gcd over wide integers (TypeScript `bigint`, Python `int`, Rust `i128`) with no range limit, used by `math.rational` to reduce intermediate products before they are checked.

Files