rng.bend

unified-nsga-iii@0.2.2.0 · 108 lines · 18 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)