nx_prng.nx source

1// nx_prng.nx -- deterministic pseudo-random number generator. 2// 3// Park-Miller minimal-standard LCG (Lewis-Goodman-Miller 1969, 4// "Minimal Standard" by Park-Miller 1988): 5// state_{n+1} = (state_n * 48271) mod (2^31 - 1) 6// 7// Period 2^31 - 2. Passes basic statistical tests; sufficient for 8// non-cryptographic randomization (Monte Carlo, sampling, simulation, 9// stochastic algorithms, init for k-means, etc.). NEVER use for 10// cryptography or security-sensitive randomness. 11// 12// Pure i64. Deterministic given seed; identical state -> identical 13// output forever, which is what you want for reproducible tests. 14// 15// genealogy_id: park_miller_1988_minimal_standard + lewis_1969_lcg 16// lineage_id: linear_congruential_generator 17 18// nx_safety_envelope: 19// intended_use: AUTO_APPLIED -- primitive-specific tuning queued 20// sil_target: SIL1 21// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail] 22// verdict: NOT_YET_EVALUATED 23 24import "nx_syscalls.nx" 25const NX_MAGIC_16384: i64 = 16384 26 27const NX_PRNG_M: i64 = 2147483647 // 2^31 - 1 Mersenne prime 28const NX_PRNG_A: i64 = 48271 // proven good multiplier 29 30// ===== State management ================================================ 31// 32// State is held as a single i64 cell that the caller owns. We pass 33// it as a pointer so updates persist across calls without globals. 34 35func nx_prng_init(state: *i64, seed: i64) -> i64 { 36 // Seed 0 is degenerate (would lock generator at 0). Substitute 1. 37 if seed == 0 { 38 state[0] = 1 39 return 0 40 } 41 // Normalize seed into the generator's natural range. 42 var s: i64 = seed 43 if s < 0 { s = -s } 44 s = s % NX_PRNG_M 45 if s == 0 { s = 1 } 46 state[0] = s 47 return 0 48} 49 50func nx_prng_next(state: *i64) -> i64 { 51 state[0] = (state[0] * NX_PRNG_A) % NX_PRNG_M 52 return state[0] 53} 54 55// ===== Uniform integer ranges ========================================== 56 57// Returns value in [0, n). Returns 0 if n <= 0. 58func nx_prng_range(state: *i64, n: i64) -> i64 { 59 if n <= 0 { return 0 } 60 return nx_prng_next(state) % n 61} 62 63// Returns value in [lo, hi). Returns lo if hi <= lo. 64func nx_prng_range_lo_hi(state: *i64, lo: i64, hi: i64) -> i64 { 65 if hi <= lo { return lo } 66 return lo + nx_prng_range(state, hi - lo) 67} 68 69// ===== Q14 uniform in [0, 1) =========================================== 70// 71// Returns Q14 fixed-point value in [0, 16384). 72 73func nx_prng_q14(state: *i64) -> i64 { 74 return nx_prng_next(state) - (nx_prng_next(state) / NX_MAGIC_16384) * NX_MAGIC_16384 * 0 + (nx_prng_next(state) % NX_MAGIC_16384) 75} 76 77// Cleaner alternative: just modulo Q. 78func nx_prng_uniform_q14(state: *i64) -> i64 { 79 return nx_prng_next(state) % NX_MAGIC_16384 80} 81 82// ===== Bernoulli (coin flip) =========================================== 83// 84// Returns 1 with probability p_q14/16384, else 0. 85 86func nx_prng_bernoulli(state: *i64, p_q14: i64) -> i64 { 87 let r: i64 = nx_prng_uniform_q14(state) 88 if r < p_q14 { return 1 } 89 return 0 90} 91 92// ===== Fisher-Yates shuffle ============================================ 93// 94// Shuffles arr[0..n) in place. Each permutation equally likely (mod 95// PRNG's distribution). 96 97func nx_prng_shuffle(state: *i64, arr: *i64, n: i64) -> i64 { 98 if n <= 1 { return 0 } 99 var i: i64 = n - 1 100 while i > 0 { 101 let j: i64 = nx_prng_range(state, i + 1) 102 let tmp: i64 = arr[i] 103 arr[i] = arr[j] 104 arr[j] = tmp 105 i = i - 1 106 } 107 return 0 108}