nx_classical_unpatented_2.nx source
↩ module page · 165 lines · 5484 B
1// nx_classical_unpatented_2.nx -- 8 more classical unpatented algorithms.
2//
3// Batch 2 of the "all non-patented open algorithms" sweep, all in pure
4// nishi-lang, all older than any plausible patent.
5
6// nx_safety_envelope:
7// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
8// sil_target: SIL1
9// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
10// verdict: NOT_YET_EVALUATED
11
12import "nx_syscalls.nx"
13import "nx_tier.nx"
14import "nx_bits.nx"
15
16// ===== 11. Count Leading Zeros (Knuth TAOCP 4A) =====================
17//
18// Delegated to nx_bits_clz64 (composes two intrinsic clz32 calls;
19// ~3 ops vs the legacy O(64) mask-shift loop). clz(0) = 64.
20// The classical Knuth pattern is preserved in the *_legacy oracle
21// for archival reference.
22func nx_clz_64(x: nx_int) -> nx_int {
23 return nx_bits_clz64(x)
24}
25
26// ===== 12. Count Trailing Zeros (Knuth TAOCP 4A) ====================
27//
28// Delegated to nx_bits_ctz64 (composes two intrinsic ctz32 calls;
29// ~3 ops vs the legacy O(64) shift loop). ctz(0) = 64.
30func nx_ctz_64(x: nx_int) -> nx_int {
31 return nx_bits_ctz64(x)
32}
33
34// ===== 13. Bit reversal (classical Knuth TAOCP 4A) ==================
35//
36// Reverse the order of bits in a 64-bit integer. Used by FFT,
37// CRC, and many bit-twiddling tricks. Public domain.
38func nx_reverse_bits_64(x: nx_int) -> nx_int {
39 var v: nx_int = x
40 var r: nx_int = 0
41 var i: nx_int = 0
42 while i < 64 {
43 r = r << 1
44 r = r | (v & 1)
45 v = v >> 1
46 i = i + 1
47 }
48 return r
49}
50
51// ===== 14. Horner polynomial evaluation (Horner, 1819) ==============
52//
53// Evaluate p(x) where coeffs is [a_0, a_1, ..., a_n-1] giving
54// p(x) = a_0 + a_1*x + a_2*x^2 + ... + a_(n-1)*x^(n-1).
55// Public domain; named after Horner 1819, known earlier as Ruffini.
56func nx_horner_eval(coeffs: *nx_int, n: nx_idx, x: nx_int) -> nx_int {
57 if n == 0 { return 0 }
58 var acc: nx_int = coeffs[n - 1]
59 var i: nx_idx = n - 1
60 while i > 0 {
61 i = i - 1
62 acc = acc * x + coeffs[i]
63 }
64 return acc
65}
66
67// ===== 15. Welford's online variance (Welford, 1962) ================
68//
69// Single-pass mean + variance of an integer array, scaled by n
70// (returns n * variance to avoid floats). Public domain;
71// Welford 1962 / Knuth TAOCP 4A.
72//
73// Returns the running sum of squared deviations (M2). Caller
74// divides by n for variance or n-1 for sample variance.
75func nx_welford_m2(arr: *nx_int, n: nx_idx) -> nx_int {
76 if n == 0 { return 0 }
77 var mean_num: nx_int = 0 // sum of values so far
78 var k: nx_int = 0
79 var m2: nx_int = 0
80 while k < (n as nx_int) {
81 let v: nx_int = arr[k]
82 let prev_mean_num: nx_int = mean_num
83 mean_num = mean_num + v
84 // delta_old = v * k - prev_mean_num (since mean_old = prev_mean_num / k)
85 // delta_new = v * (k+1) - mean_num
86 // Welford on integers: m2 += (v*k - prev_mean_num) * (v*(k+1) - mean_num) / (k*(k+1))
87 // Reformulated to integer-safe: use the standard incremental form
88 // but track everything as numerators.
89 if k > 0 {
90 let delta1: nx_int = v * k - prev_mean_num
91 let delta2: nx_int = v * (k + 1) - mean_num
92 m2 = m2 + delta1 * delta2 / (k * (k + 1))
93 }
94 k = k + 1
95 }
96 return m2
97}
98
99// ===== 16. Extended Euclidean (Bezout coefficients) ================
100//
101// Computes g = gcd(a, b) and (x, y) such that a*x + b*y = g.
102// Public domain; classical extension of Euclid's algorithm.
103// Returns g; writes x to out_x, y to out_y.
104func nx_extended_gcd(a: nx_int, b: nx_int, out_x: *nx_int, out_y: *nx_int) -> nx_int {
105 var old_r: nx_int = a
106 var r: nx_int = b
107 var old_s: nx_int = 1
108 var s: nx_int = 0
109 var old_t: nx_int = 0
110 var t: nx_int = 1
111 while r != 0 {
112 let q: nx_int = old_r / r
113 let tmp_r: nx_int = old_r - q * r
114 old_r = r; r = tmp_r
115 let tmp_s: nx_int = old_s - q * s
116 old_s = s; s = tmp_s
117 let tmp_t: nx_int = old_t - q * t
118 old_t = t; t = tmp_t
119 }
120 out_x[0] = old_s
121 out_y[0] = old_t
122 return old_r
123}
124
125// ===== 17. Modular exponentiation by squaring (classical) ==========
126//
127// Computes base^exp mod m in O(log exp). Foundation of RSA, primality
128// testing, and lots of crypto. The squaring trick predates patents.
129// Returns 0 if m == 0 (caller error).
130func nx_mod_pow(base: nx_int, exp: nx_int, m: nx_int) -> nx_int {
131 if m == 0 { return 0 }
132 if m == 1 { return 0 }
133 var result: nx_int = 1
134 var b: nx_int = base - (base / m) * m // base mod m
135 var e: nx_int = exp
136 while e > 0 {
137 if (e & 1) == 1 {
138 result = (result * b) - ((result * b) / m) * m
139 }
140 e = e >> 1
141 b = (b * b) - ((b * b) / m) * m
142 }
143 return result
144}
145
146// ===== 18. Primality by trial division (folklore, c. Eratosthenes) =
147//
148// Returns 1 if n is prime, 0 otherwise. O(sqrt n) by trial division.
149// Public domain since antiquity. For larger n, use Miller-Rabin
150// (also unpatented but more complex).
151func nx_is_prime_trial(n: nx_int) -> nx_int {
152 if n < 2 { return 0 }
153 if n == 2 { return 1 }
154 if (n & 1) == 0 { return 0 } // even, not prime
155 var i: nx_int = 3
156 var done: nx_int = 0
157 while done == 0 {
158 if i * i > n { done = 1 }
159 if done == 0 {
160 if (n - (n / i) * i) == 0 { return 0 }
161 i = i + 2
162 }
163 }
164 return 1
165}