nx_lcm.nx source
↩ module page · 31 lines · 1012 B
1// nx_lcm.nx -- least common multiple via Euclidean GCD.
2//
3// genealogy_id: euclid_lcm_gcd_identity
4// lineage_id: number_theory_composition
5// references: Euclid Elements Book VII (lcm*gcd = ab identity).
6// license: public_domain
7// complexity: O(log min(a, b)) -- inherits nx_gcd.
8
9// nx_safety_envelope:
10// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
11// sil_target: SIL1
12// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
13// verdict: NOT_YET_EVALUATED
14
15import "nx_syscalls.nx"
16import "nx_tier.nx"
17import "nx_gcd.nx"
18
19// Least common multiple of two non-negative integers.
20// lcm(0, x) = 0 by convention.
21func nx_lcm(a: nx_int, b: nx_int) -> nx_int {
22 if a == 0 { return 0 }
23 if b == 0 { return 0 }
24 var x: nx_int = a
25 var y: nx_int = b
26 if x < 0 { x = 0 - x }
27 if y < 0 { y = 0 - y }
28 let g: nx_int = nx_gcd(x, y)
29 // Divide by gcd first to avoid overflow vs (a*b)/g.
30 return (x / g) * y
31}