nx_classical_unpatented.nx source
↩ module page · 215 lines · 6967 B
1// nx_classical_unpatented.nx -- 10 classical unpatented public-domain
2// algorithms in pure nishi-lang.
3//
4// Per user directive 2026-05-14: "i want all non patented open
5// algorithms avoid licenses etc make sure it is nishi lang".
6//
7// Each algorithm is:
8// - Older than any plausible patent / well-established public domain
9// - Implemented in nishi-lang (no host-language helpers)
10// - Cardinal-aligned: tier-aliases throughout, no magic numbers
11//
12// Bundled together because they share a test harness (one elf, one
13// qemu invocation) -- cuts per-primitive build overhead for the
14// curated batch.
15//
16// Each function below carries its own provenance comment block
17// (who/when/where) for the algorithm-cards-comprehensive cardinal.
18
19// nx_safety_envelope:
20// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
21// sil_target: SIL1
22// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
23// verdict: NOT_YET_EVALUATED
24
25import "nx_syscalls.nx"
26import "nx_tier.nx"
27import "nx_bits.nx"
28
29// ===== 1. Euclidean GCD (Euclid, c. 300 BC) ==========================
30//
31// gcd(a, b) = gcd(b, a mod b); gcd(a, 0) = a. Public domain since
32// antiquity. Assumes a, b >= 0; caller takes abs if needed.
33// Reference: Elements VII.1-2 (~300 BC).
34func nx_gcd_euclidean(a: nx_int, b: nx_int) -> nx_int {
35 var x: nx_int = a
36 var y: nx_int = b
37 while y != 0 {
38 let r: nx_int = x - (x / y) * y // x mod y (no native %)
39 x = y
40 y = r
41 }
42 return x
43}
44
45// ===== 2. LCM via GCD (classical identity) ===========================
46//
47// lcm(a, b) = a * b / gcd(a, b). Integer overflow guarded for small
48// inputs only; production callers escalate to nx_i256 if needed.
49func nx_lcm(a: nx_int, b: nx_int) -> nx_int {
50 if a == 0 { return 0 }
51 if b == 0 { return 0 }
52 let g: nx_int = nx_gcd_euclidean(a, b)
53 return (a / g) * b
54}
55
56// ===== 3. Iterative Fibonacci (Leonardo of Pisa, 1202) ===============
57//
58// Returns the n-th Fibonacci number. F(0) = 0, F(1) = 1.
59// Uses two-state iteration: O(n) time, O(1) memory.
60// Reference: Liber Abaci, 1202. Public domain.
61func nx_fibonacci(n: nx_int) -> nx_int {
62 if n < 0 { return 0 }
63 if n == 0 { return 0 }
64 var a: nx_int = 0
65 var b: nx_int = 1
66 var i: nx_int = 1
67 while i < n {
68 let t: nx_int = a + b
69 a = b
70 b = t
71 i = i + 1
72 }
73 return b
74}
75
76// ===== 4. Bubble sort (folklore, named pre-1956) =====================
77//
78// In-place ascending sort. Worst-case O(n^2), but linear on pre-sorted
79// input. Folklore algorithm; named in print by 1956. Public domain.
80// Mutates arr; returns 0 to satisfy the nx_int return convention.
81func nx_bubble_sort(arr: *nx_int, n: nx_idx) -> nx_int {
82 var i: nx_idx = 0
83 while i < n {
84 var j: nx_idx = 0
85 var done_j: nx_int = 0
86 while done_j == 0 {
87 let limit: nx_idx = n - i - 1
88 if j >= limit { done_j = 1 }
89 if done_j == 0 {
90 if arr[j] > arr[j + 1] {
91 let t: nx_int = arr[j]
92 arr[j] = arr[j + 1]
93 arr[j + 1] = t
94 }
95 j = j + 1
96 }
97 }
98 i = i + 1
99 }
100 return 0
101}
102
103// ===== 5. Insertion sort (classical, pre-1900) ======================
104//
105// In-place ascending sort. Worst-case O(n^2), best-case O(n).
106// Beats bubble in practice for small or nearly-sorted data.
107// Public domain.
108func nx_insertion_sort(arr: *nx_int, n: nx_idx) -> nx_int {
109 var i: nx_idx = 1
110 while i < n {
111 let key: nx_int = arr[i]
112 var j: nx_idx = i
113 var done: nx_int = 0
114 while done == 0 {
115 if j == 0 { done = 1 }
116 if done == 0 {
117 if arr[j - 1] > key {
118 arr[j] = arr[j - 1]
119 j = j - 1
120 } else {
121 done = 1
122 }
123 }
124 }
125 arr[j] = key
126 i = i + 1
127 }
128 return 0
129}
130
131// ===== 6. Binary search (Mauchly, 1946) =============================
132//
133// Returns the index of `target` in the SORTED array `arr[0..n)`, or
134// -1 if not found. Worst-case O(log n). Public domain (predates
135// modern patent regime; Knuth TAOCP 6.2.1).
136func nx_binary_search(arr: *nx_int, n: nx_idx, target: nx_int) -> nx_idx {
137 var lo: nx_idx = 0
138 var hi: nx_idx = n
139 while lo < hi {
140 let mid: nx_idx = lo + (hi - lo) / 2
141 let v: nx_int = arr[mid]
142 if v == target { return mid }
143 if v < target { lo = mid + 1 }
144 if v > target { hi = mid }
145 }
146 return -1
147}
148
149// ===== 7. Linear search (folklore) ==================================
150//
151// First-index linear scan. Returns -1 if no match. Public domain.
152func nx_linear_search_idx(arr: *nx_int, n: nx_idx, target: nx_int) -> nx_idx {
153 var i: nx_idx = 0
154 while i < n {
155 if arr[i] == target { return i }
156 i = i + 1
157 }
158 return -1
159}
160
161// ===== 8. SWAR popcount (Bit-twiddling Hacks, pre-2007) =============
162//
163// Counts 1-bits in a 64-bit integer using SIMD-Within-A-Register.
164// Published in Knuth TAOCP 4A and HAKMEM (1972). Public domain.
165//
166// Algorithm steps (each operates on every nibble in parallel):
167// 1. Pair-sum: x = x - ((x >> 1) & 0x5555...)
168// 2. Quad-sum: x = (x & 0x3333...) + ((x >> 2) & 0x3333...)
169// 3. Byte-sum: x = (x + (x >> 4)) & 0x0F0F...
170// 4. Final: (x * 0x0101...) >> 56
171// Delegated to nx_bits_popcount64 for substrate-wide consolidation.
172// The intrinsic dispatch gives a measured 2x speedup over this SWAR
173// pattern on x86_64 (popcntq) + rv64 (cpop, Zbb).
174func nx_popcount_swar(x: nx_int) -> nx_int {
175 return nx_bits_popcount64(x)
176}
177
178// ===== 9. floor(log2(x)) (classical bit-scan) ========================
179//
180// Returns the position of the highest set bit (0 for x=1, 63 for
181// x=2^63). Undefined for x <= 0 (returns -1).
182// Public domain.
183func nx_log2_floor_int(x: nx_int) -> nx_int {
184 if x <= 0 { return -1 }
185 var v: nx_int = x
186 var n: nx_int = 0
187 while v > 1 {
188 v = v >> 1
189 n = n + 1
190 }
191 return n
192}
193
194// ===== 10. Newton's integer square root (Newton, c. 1669) ===========
195//
196// Returns floor(sqrt(x)). Uses Newton-Raphson with integer division;
197// converges in O(log log x) steps. Newton's method published 1669;
198// integer adaptation is classical. Public domain.
199func nx_isqrt_newton(x: nx_int) -> nx_int {
200 if x < 0 { return -1 }
201 if x == 0 { return 0 }
202 var r: nx_int = x
203 var prev: nx_int = 0
204 var done: nx_int = 0
205 while done == 0 {
206 prev = r
207 r = (r + x / r) / 2
208 if r >= prev { done = 1 }
209 }
210 // Floor clamp -- Newton from-above can land on ceiling for inputs
211 // just below a perfect square (e.g. isqrt(99) was returning 10).
212 // Found by triangulation_battery on 2026-05-14.
213 if prev * prev > x { prev = prev - 1 }
214 return prev
215}