rng.bend
unified-nsga-iii@0.2.0.0 · 108 lines · 0 definitions
1# RandomProvider surface — C# Unsga3.Utilities.RandomProvider.
2# Seed + NextDouble in [0, 1) + Next / NextExcept for tournament.
3# Portable Numerical Recipes LCG (not .NET System.Random). Algorithm
4# A/B fronts will not match C# bit-for-bit because of this RNG delta.
5#
6# Affine API: `next_double` / `next_nat` return the advanced state;
7# `last_double` / `last_nat` are that draw. Callers use lets, not
8# pair-destructure.
9
10import Base
11
12type State is Data:
13 MkState{
14 s0: U32
15 u: U32
16 z: F32
17 k: Nat
18 }
19
20def new(+s0: U32) -> State:
21 MkState{s0, s0, 0.0, 0n}
22
23def from_nat(seed: Nat) -> State:
24 new(U32.from_nat(seed))
25
26def seed_of(s: State) -> U32:
27 match s:
28 case MkState{s0, u, z, k}:
29 s0
30
31def last_double(s: State) -> F32:
32 match s:
33 case MkState{s0, u, z, k}:
34 z
35
36def last_nat(s: State) -> Nat:
37 match s:
38 case MkState{s0, u, z, k}:
39 k
40
41def step(u: U32) -> U32:
42 U32.add(U32.mul(1664525, u), 1013904223)
43
44# Top 24 bits / 2^24 so the F32 mantissa is exact and the value is in [0, 1).
45def to_unit(u: U32) -> F32:
46 F32.div(U32.to_f32(U32.shrn(u, 8n)), 16777216.0)
47
48def next_double(s: State) -> State:
49 match s:
50 case MkState{s0, u, z, k}:
51 +n = step(u)
52 MkState{s0, n, to_unit(n), k}
53
54def pred_or_zero(n: Nat) -> Nat:
55 match n:
56 case 0n:
57 0n
58 case 1n+p:
59 p
60
61def clamp_lt.fin(+i: Nat, +n: Nat, ok: Bool) -> Nat:
62 match ok:
63 case True{}:
64 i
65 case False{}:
66 pred_or_zero(n)
67
68def clamp_lt(+i: Nat, +n: Nat) -> Nat:
69 clamp_lt.fin(i, n, Nat.is_lt(i, n))
70
71def idx_from(+z: F32, n: Nat) -> Nat:
72 match n:
73 case 0n:
74 0n
75 case 1n++p:
76 clamp_lt(F32.to_nat(F32.trunc(F32.mul(z, F32.from_nat(1n+p)))), 1n+p)
77
78def with_k(s: State, k2: Nat) -> State:
79 match s:
80 case MkState{s0, u, z, k}:
81 MkState{s0, u, z, k2}
82
83# Uniform integer in [0, n). n == 0n → 0n.
84def next_nat(s: State, n: Nat) -> State:
85 +s2 = next_double(s)
86 with_k(s2, idx_from(last_double(s2), n))
87
88def bump_except(+v: Nat, +exclude: Nat, below: Bool) -> Nat:
89 match below:
90 case True{}:
91 v
92 case False{}:
93 1n+v
94
95# C# NextExcept: uniform in [0, n) distinct from exclude when n > 1.
96def next_except.go(s: State, +exclude: Nat, n: Nat) -> State:
97 match n:
98 case 0n:
99 with_k(s, 0n)
100 case 1n:
101 with_k(s, 0n)
102 case 1n+m:
103 +s2 = next_nat(s, m)
104 +v = last_nat(s2)
105 with_k(s2, bump_except(v, exclude, Nat.is_lt(v, exclude)))
106
107def next_except(s: State, n: Nat, exclude: Nat) -> State:
108 next_except.go(s, exclude, n)