Janady13/feedthejoe / src/core/rank/random.js

1/** 2 * Seeded pseudo-randomness. 3 * 4 * The recommender is stochastic by design — Thompson sampling needs draws from 5 * a Beta posterior. Stochastic is not the same as untestable: every draw in 6 * this system comes from an explicit, injected generator, so a test can pin the 7 * seed and assert an exact ordering. 8 * 9 * Nothing here touches Math.random(). That is deliberate and load-bearing. 10 */ 11 12/** 13 * mulberry32 — a 32-bit PRNG with a full 2^32 period and good statistical 14 * properties for our purposes (we need plausible jitter, not cryptography). 15 * 16 * @param {number} seed Any integer. 17 * @returns {() => number} Generator yielding floats in [0, 1). 18 */ 19export function mulberry32(seed) { 20 let a = seed >>> 0; 21 return function next() { 22 a = (a + 0x6d2b79f5) >>> 0; 23 let t = a; 24 t = Math.imul(t ^ (t >>> 15), 1 | t); 25 t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; 26 return ((t ^ (t >>> 14)) >>> 0) / 4294967296; 27 }; 28} 29 30/** 31 * Derive a stable 32-bit seed from a string, so an item id maps to the same 32 * jitter on every render. FNV-1a. 33 * 34 * @param {string} str 35 * @returns {number} 36 */ 37export function seedFrom(str) { 38 let h = 2166136261 >>> 0; 39 for (let i = 0; i < str.length; i += 1) { 40 h ^= str.charCodeAt(i); 41 h = Math.imul(h, 16777619) >>> 0; 42 } 43 return h >>> 0; 44} 45 46/** 47 * Standard normal deviate via the Box–Muller transform. 48 * 49 * @param {() => number} rng 50 * @returns {number} 51 */ 52export function gaussian(rng) { 53 // u must be non-zero for log(); the half-open range of rng() makes 0 possible. 54 let u = 0; 55 while (u === 0) u = rng(); 56 const v = rng(); 57 return Math.sqrt(-2 * Math.log(u)) * Math.cos(2 * Math.PI * v); 58} 59 60/** 61 * Gamma(shape, 1) draw via Marsaglia & Tsang (2000), "A Simple Method for 62 * Generating Gamma Variables", ACM TOMS 26(3). 63 * 64 * The method is defined for shape >= 1; for shape < 1 we use the standard 65 * boost identity G(a) = G(a+1) * U^(1/a). 66 * 67 * @param {() => number} rng 68 * @param {number} shape Must be > 0. 69 * @returns {number} 70 */ 71export function gammaSample(rng, shape) { 72 if (!(shape > 0)) throw new RangeError(`gammaSample: shape must be > 0, got ${shape}`); 73 74 if (shape < 1) { 75 const u = Math.max(rng(), Number.MIN_VALUE); 76 return gammaSample(rng, shape + 1) * Math.pow(u, 1 / shape); 77 } 78 79 const d = shape - 1 / 3; 80 const c = 1 / Math.sqrt(9 * d); 81 82 // Rejection loop. Expected iterations is < 1.01 for all shape >= 1, so this 83 // terminates promptly; there is no unbounded-loop risk in practice. 84 for (;;) { 85 let x; 86 let v; 87 do { 88 x = gaussian(rng); 89 v = 1 + c * x; 90 } while (v <= 0); 91 92 v = v * v * v; 93 const u = rng(); 94 const x2 = x * x; 95 96 // Squeeze: cheap acceptance test that avoids the logarithms most of the time. 97 if (u < 1 - 0.0331 * x2 * x2) return d * v; 98 if (Math.log(u) < 0.5 * x2 + d * (1 - v + Math.log(v))) return d * v; 99 } 100} 101 102/** 103 * Beta(alpha, beta) draw, built from two Gamma draws: 104 * X ~ G(a,1), Y ~ G(b,1) => X / (X + Y) ~ Beta(a, b) 105 * 106 * This is the sampling primitive behind Thompson sampling: each topic carries a 107 * Beta posterior over "will this visitor engage", and we rank by a draw from it 108 * rather than by its mean. Sampling is what produces exploration — a topic with 109 * little evidence has a wide posterior and will sometimes draw high, which is 110 * exactly the cold-start promotion behaviour we want. 111 * 112 * @param {() => number} rng 113 * @param {number} alpha Successes + prior. Must be > 0. 114 * @param {number} beta Failures + prior. Must be > 0. 115 * @returns {number} A value in [0, 1]. 116 */ 117export function betaSample(rng, alpha, beta) { 118 const x = gammaSample(rng, alpha); 119 const y = gammaSample(rng, beta); 120 const sum = x + y; 121 // Both gammas underflowing to 0 is astronomically unlikely but not impossible; 122 // fall back to the posterior mean rather than emitting NaN. 123 if (sum === 0) return alpha / (alpha + beta); 124 return x / sum; 125} 126