math.gcd-lcm

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

/** 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;
}

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

import { type GcdLcm } from "./math_gcd_lcm_types.ts";

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. Never negative; gcdWide(0, 0) is 0. */
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;
}

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 {
  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);
}

/**
 * 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) };
}

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

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

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