nx_gcd.nx source
↩ module page · 32 lines · 1035 B
1// nx_gcd.nx -- Euclid's algorithm for greatest common divisor.
2//
3// genealogy_id: euclid_300bc_elements_book_vii
4// lineage_id: number_theory_foundation
5// references: Euclid Elements Book VII Prop 2 (c. 300 BC);
6// Knuth TAoCP Vol 2 4.5.2.
7// license: public_domain (2300+ year-old result)
8// complexity: O(log min(a, b)) division steps.
9
10// nx_safety_envelope:
11// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
12// sil_target: SIL1
13// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
14// verdict: NOT_YET_EVALUATED
15
16import "nx_syscalls.nx"
17import "nx_tier.nx"
18
19// Greatest common divisor of two non-negative integers.
20// gcd(a, 0) = a; gcd(0, b) = b.
21func nx_gcd(a: nx_int, b: nx_int) -> nx_int {
22 var x: nx_int = a
23 var y: nx_int = b
24 if x < 0 { x = 0 - x }
25 if y < 0 { y = 0 - y }
26 while y != 0 {
27 let r: nx_int = x - (x / y) * y // x mod y
28 x = y
29 y = r
30 }
31 return x
32}