src/math/random.bend

bend-collections@1.0.0.0 · 93 lines · 16 definitions

1import Base
2import bend-collections@1.0.0.0/src/math/u64.bend as W
3import bend-collections@1.0.0.0/src/math/f64.bend as F
4import bend-collections@1.0.0.0/src/math/random/rand.bend as R
5import bend-collections@1.0.0.0/src/math/random/chacha8.bend as C8
6import bend-collections@1.0.0.0/src/math/random/pcg.bend as P
7
8# Pseudorandom numbers, shaped like Go's math/rand/v2: a generator is a value
9# built from a seed the caller chooses (the same seed gives the same
10# sequence, bit for bit Go's), threaded explicitly: every call returns its
11# value next to the advanced generator.
12#
13#   import ./src/math/random.bend as R
14#   import ./src/math/random/pcg.bend as PCG           (the state types:
15#   import ./src/math/random/chacha8.bend as C8         PCG.PCG, C8.ChaCha8)
16#
17#   R.pcg(W.U64{1, 0}, W.U64{2, 0})                   Go: rand.NewPCG(1, 2)
18#   R.uint64n(~PCG.PCG, ~R.pcg_next, g, n)            Go: r.Uint64N(n)
19#   R.shuffle(~U32, ~PCG.PCG, ~R.pcg_next, g, xs)     Go: r.Shuffle
20#
21# (each call returns the value next to the advanced generator: a pair, taken
22# apart in a helper def, as Bend matches only parameters)
23#
24# Sources (the Source interface of random/rand.bend: a state type S and
25# ~next: S -> W.U64 & S, passed as templates):
26#
27#   chacha8(seed), chacha8_next   Go's ChaCha8 = C2SP chacha8rand, a 32-byte
28#                                 seed (None unless 32 bytes < 256); a CSPRNG
29#                                 (for secrets use src/crypto/random.bend)
30#   pcg(seed1, seed2), pcg_next   Go's PCG (128-bit LCG, DXSM output); fast,
31#                                 not cryptographic
32#
33# Functions over any source (random/rand.bend has the details):
34#
35#   uint64 uint32 int64 int32     raw words
36#   uint64n / uint_below, uint32n, intn, int_range
37#                                 uniform bounded integers (Lemire, unbiased)
38#   float64                       uniform in [0, 1), 53 random bits
39#   shuffle, perm                 Fisher-Yates
40#
41# Laws (spec/math/random/, proved in proofs/math/random/): the ChaCha8
42# stream is C2SP's for every seed, one PCG step is the 128-bit LCG and DXSM
43# on naturals, uint64n(n) < n, Lemire's acceptance is exactly unbiased
44# (every k < n has floor(2^64 / n) accepted inputs), shuffle and perm return
45# permutations, float64 < 1.
46
47def chacha8(+seed: List<&2, U32>) -> Maybe<&2, C8.ChaCha8>:
48  C8.new(seed)
49
50def chacha8_next(g: C8.ChaCha8) -> W.U64 & C8.ChaCha8:
51  C8.next(g)
52
53def pcg(+seed1: W.U64, +seed2: W.U64) -> P.PCG:
54  P.new(seed1, seed2)
55
56def pcg_next(p: P.PCG) -> W.U64 & P.PCG:
57  P.next(p)
58
59def uint64(~S: Data, ~next: S -> W.U64 & S, s: S) -> W.U64 & S:
60  R.uint64(~S, ~next, s)
61
62def uint32(~S: Data, ~next: S -> W.U64 & S, s: S) -> U32 & S:
63  R.uint32(~S, ~next, s)
64
65def int64(~S: Data, ~next: S -> W.U64 & S, s: S) -> W.U64 & S:
66  R.int64(~S, ~next, s)
67
68def int32(~S: Data, ~next: S -> W.U64 & S, s: S) -> U32 & S:
69  R.int32(~S, ~next, s)
70
71def uint64n(~S: Data, ~next: S -> W.U64 & S, s: S, +n: W.U64) -> W.U64 & S:
72  R.uint64n(~S, ~next, s, n)
73
74def uint_below(~S: Data, ~next: S -> W.U64 & S, s: S, +n: W.U64) -> W.U64 & S:
75  R.uint64n(~S, ~next, s, n)
76
77def uint32n(~S: Data, ~next: S -> W.U64 & S, s: S, +n: U32) -> U32 & S:
78  R.uint32n(~S, ~next, s, n)
79
80def intn(~S: Data, ~next: S -> W.U64 & S, s: S, +n: Nat) -> Nat & S:
81  R.intn(~S, ~next, s, n)
82
83def int_range(~S: Data, ~next: S -> W.U64 & S, s: S, +lo: Nat, +hi: Nat) -> Nat & S:
84  R.int_range(~S, ~next, s, lo, hi)
85
86def float64(~S: Data, ~next: S -> W.U64 & S, s: S) -> F.F64 & S:
87  R.float64(~S, ~next, s)
88
89def shuffle(~A: Data, ~S: Data, ~next: S -> W.U64 & S, s: S, +xs: List<&2, A>) -> List<&2, A> & S:
90  R.shuffle(~A, ~S, ~next, s, xs)
91
92def perm(~S: Data, ~next: S -> W.U64 & S, s: S, +n: Nat) -> List<&2, Nat> & S:
93  R.perm(~S, ~next, s, n)