math.gcd-lcm

/** Both answers together; each is never negative. */
export interface GcdLcm {
  /** greatest common divisor; gcd(0, 0) is 0 */
  readonly gcd: number;
  /** least common multiple; 0 when either input is 0 */
  readonly lcm: number;
}

export function gcdLcm(a: number, b: number): GcdLcm

import { gcdLcm } from "#fune/math.gcd-lcm@^2";

import { gcd } from "./math_gcd_lcm_gcd.ts";  ← gcd, another function of this group · built into the same file, even by a slim install
import { lcm } from "./math_gcd_lcm_lcm.ts";  ← lcm, another function of this group · built into the same file, even by a slim install
import { type GcdLcm } from "./math_gcd_lcm_types.ts";

/**
 * 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).
 */
export function gcdLcm(a: number, b: number): GcdLcm {
  return { gcd: gcd(a, b), lcm: lcm(a, b) };
}

export function gcd(a: number, b: number): number

import { gcd } from "#fune/math.gcd-lcm@^2";

function checkSafe(name: string, value: number): void {
  if (!Number.isInteger(value)) {
    throw new TypeError(`${name} must be an integer, received ${value}`);
  }
  if (!Number.isSafeInteger(value)) {
    throw new RangeError(`${name} is outside the safe integer range (±9007199254740991)`);
  }
}

/**
 * Euclid's algorithm on wide integers, with no range limit. Never negative;
 * gcdWide(0, 0) is 0. Exported for fraction arithmetic (math.rational), which
 * reduces products that are already past 2^53 before it checks them.
 */
export function gcdWide(a: bigint, b: bigint): bigint {
  let x = a < 0n ? -a : a;
  let y = b < 0n ? -b : b;
  while (y !== 0n) {
    const r = x % y;
    x = y;
    y = r;
  }
  return x;
}

/** Greatest common divisor, never negative; gcd(0, n) is |n| and gcd(0, 0) is 0. */
export function gcd(a: number, b: number): number {
  checkSafe("a", a);
  checkSafe("b", b);
  return Number(gcdWide(BigInt(a), BigInt(b)));
}

export function lcm(a: number, b: number): number

import { lcm } from "#fune/math.gcd-lcm@^2";

import { gcd } from "./math_gcd_lcm_gcd.ts";  ← gcd, another function of this group · built into the same file, even by a slim install

/** Least common multiple, never negative; 0 when either input is 0. */
export function lcm(a: number, b: number): number {
  const g = gcd(a, b);
  if (g === 0) return 0;
  // Divide before multiplying: a * b overflows long before the lcm does.
  const result = (BigInt(Math.abs(a)) / BigInt(g)) * BigInt(Math.abs(b));
  if (result > BigInt(Number.MAX_SAFE_INTEGER)) {
    throw new RangeError(`the lcm of ${a} and ${b} exceeds 2^53 - 1`);
  }
  return Number(result);
}

Install

fune build

With that line in your source, in a TypeScript project (language typescript in fune.project), fune build resolves it and nothing else, pins them in fune.lock, downloads only the TypeScript 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

That builds the whole group. To build only what you call, and whatever it uses inside the group:

fune add math.gcd-lcm --only gcdLcm

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

The whole function, every language, is one file too: math.gcd-lcm-2.0.0.fune, 19,234 bytes, sha256 b4ff66bde30ed40b4e53d980014fb8902c3854539d276a87c0c083ba74f7a1bb. It installs into a project of any language.

// fune: before math.gcd-lcm.gcdLcm
// fune: before math.gcd-lcm.gcd
// fune: before math.gcd-lcm.lcm

// fune: after math.gcd-lcm.gcdLcm
// fune: after math.gcd-lcm.gcd
// fune: after math.gcd-lcm.lcm

// fune: step math.gcd-lcm.<fn> 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.

This is a group of three functions: `gcdLcm(a, b)` returns both answers, `gcd(a, b)` and `lcm(a, b)` one each. `lcm` uses `gcd`, and `gcdLcm` uses both, so `require math.gcd-lcm ^2.0.0 only=gcd` installs the gcd alone.

`gcdWide(a, b)`, a gcd over wide integers (TypeScript `bigint`, Python `int`, Rust `i128`) with no range limit, is still exported from the `gcd` file for fraction arithmetic that reduces products already past 2^53. It is a helper, not a published function: the registry's type vocabulary has no wide integer (`int` is a JavaScript number and an `i64`), so it has no `fn` line and no vectors of its own, and it is exercised through `gcd`'s vectors. Its signature and behaviour are exactly those of 1.0.0.

## What changed from 1.0.0

1.0.0 was one function, `gcdLcm`, with `gcd`, `lcm` and `gcdWide` exported alongside it but unpinned: no signature in the manifest and no vectors, so nothing held the three languages to the same answer for them. 2.0.0 is a group: `gcd` and `lcm` are published functions with their own signatures, files and vectors, and `gcdLcm` keeps every 1.0.0 vector.

No answer changed. The Rust adapters now refuse a fractional argument with the same "must be an integer" wording as TypeScript and Python, which only affects the vectors. It is a new major version because the package's shape and public surface changed: it installs as one module per function plus the group module (`math_gcd_lcm` still re-exports every function and `gcdWide`), a project can take only some of it, and the Python module no longer exports its `MAX_SAFE` constant. Dependents stay on `^1.0.0` until they move deliberately; 1.0.0 is unchanged.

Files