nx_extended_gcd.nx source
↩ module page · 45 lines · 1455 B
1// nx_extended_gcd.nx -- extended Euclidean: gcd + Bezout coefficients.
2//
3// genealogy_id: knuth_taocp_4_5_2_algorithm_x
4// lineage_id: number_theory_foundation
5// references: Bezout 1624 (identity); Knuth TAoCP Vol 2 4.5.2 Algorithm X.
6// license: public_domain
7// complexity: O(log min(a, b)) divisions.
8//
9// Tier discipline: arithmetic values are nx_int; pointers carry the
10// same type so swapping the substrate tier carries through.
11
12// nx_safety_envelope:
13// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
14// sil_target: SIL1
15// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
16// verdict: NOT_YET_EVALUATED
17
18import "nx_syscalls.nx"
19import "nx_tier.nx"
20
21// Returns gcd(a, b); writes Bezout coefficients to *x_out, *y_out
22// such that a * x_out[0] + b * y_out[0] == gcd(a, b).
23func nx_extended_gcd(a: nx_int, b: nx_int, x_out: *nx_int, y_out: *nx_int) -> nx_int {
24 var old_r: nx_int = a
25 var r: nx_int = b
26 var old_s: nx_int = 1
27 var s: nx_int = 0
28 var old_t: nx_int = 0
29 var t: nx_int = 1
30 while r != 0 {
31 let q: nx_int = old_r / r
32 let tmp_r: nx_int = old_r - q * r
33 old_r = r
34 r = tmp_r
35 let tmp_s: nx_int = old_s - q * s
36 old_s = s
37 s = tmp_s
38 let tmp_t: nx_int = old_t - q * t
39 old_t = t
40 t = tmp_t
41 }
42 x_out[0] = old_s
43 y_out[0] = old_t
44 return old_r
45}