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	
10	import Base
11	
12	type State is Data:
13	  MkState{
14	    s0: U32
15	    u: U32
16	    z: F32
17	    k: Nat
18	  }
19	
20	def new(+s0: U32) -> State:
21	  MkState{s0, s0, 0.0, 0n}
22	
23	def from_nat(seed: Nat) -> State:
24	  new(U32.from_nat(seed))
25	
26	def seed_of(s: State) -> U32:
27	  match s:
28	    case MkState{s0, u, z, k}:
29	      s0
30	
31	def last_double(s: State) -> F32:
32	  match s:
33	    case MkState{s0, u, z, k}:
34	      z
35	
36	def last_nat(s: State) -> Nat:
37	  match s:
38	    case MkState{s0, u, z, k}:
39	      k
40	
41	def 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).
45	def to_unit(u: U32) -> F32:
46	  F32.div(U32.to_f32(U32.shrn(u, 8n)), 16777216.0)
47	
48	def 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	
54	def pred_or_zero(n: Nat) -> Nat:
55	  match n:
56	    case 0n:
57	      0n
58	    case 1n+p:
59	      p
60	
61	def 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	
68	def clamp_lt(+i: Nat, +n: Nat) -> Nat:
69	  clamp_lt.fin(i, n, Nat.is_lt(i, n))
70	
71	def 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	
78	def 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.
84	def next_nat(s: State, n: Nat) -> State:
85	  +s2 = next_double(s)
86	  with_k(s2, idx_from(last_double(s2), n))
87	
88	def 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.
96	def 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	
107	def next_except(s: State, n: Nat, exclude: Nat) -> State:
108	  next_except.go(s, exclude, n)