src/math/random/rand.bend checks

raw source on the hub · import bend-collections-laws-math@1.0.0.0/src/math/random/rand.bend as Rand

4 imports

import Base
import ../u64.bend as W
import ../w64.bend as X
import ../f64.bend as F

Types

type Draw source · line 108 · raw

@-S:Data -> Data

the draw x as the product x * n = hi:lo, kept with the state

D

@-S:Data -> @hi:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @lo:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @s:S -> Draw<S>

Definitions

def fst source · line 58 · raw

@-A:Data -> @-S:Data -> @p:Pair(A, S) -> A

def snd source · line 62 · raw

@-A:Data -> @-S:Data -> @p:Pair(A, S) -> S

def top32 source · line 69 · raw

@-S:Data -> @p:Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S) -> Pair(U32, S)

def low63 source · line 76 · raw

@-S:Data -> @p:Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S) -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)

def top31 source · line 83 · raw

@-S:Data -> @p:Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S) -> Pair(U32, S)

def and64 source · line 92 · raw

@+a:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @+b:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64

def is_pow2 source · line 96 · raw

@+n:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> Bool

n & (n - 1) == 0: n is a power of two (or zero)

def mask source · line 99 · raw

@-S:Data -> @+n:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @p:Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S) -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)

def thresh source · line 104 · raw

@+n:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64

2^64 mod n = (2^64 - n) mod n, for n > 0 (Go: -n % n)

def draw_fin source · line 111 · raw

@-S:Data -> @s:S -> @p:Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64) -> Draw<S>

def draw source · line 115 · raw

@-S:Data -> @+n:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @p:Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S) -> Draw<S>

def result source · line 140 · raw

@-S:Data -> @d:Draw<S> -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)

def lo32 source · line 173 · raw

@-S:Data -> @p:Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S) -> Pair(U32, S)

def w_go source · line 182 · raw

@k:Nat -> @+n:Nat -> U32

the 32-bit word of the low 8k bits of n, a byte at a time

def skip source · line 190 · raw

@k:Nat -> @+n:Nat -> Nat

n div 2^(8k)

def nat64 source · line 198 · raw

@+n:Nat -> 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64

the 64-bit word of n < 2^64

def to_nat source · line 201 · raw

@-S:Data -> @p:Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S) -> Pair(Nat, S)

def plus source · line 216 · raw

@-S:Data -> @+lo:Nat -> @p:Pair(Nat, S) -> Pair(Nat, S)

def f53 source · line 229 · raw

@+m:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @+c:Nat -> 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/f64.F64

x >> 11 as a double divided by 2^53: for m = x >> 11 > 0 with c leading zeros (11 <= c <= 63), m << (c - 11) has its top bit at 52, and the value m 2^-53 is that significand with biased exponent 1033 - c (below 1023)

def f53_z source · line 232 · raw

@+m:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @z:Bool -> 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/f64.F64

def to_float source · line 240 · raw

@+x:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/f64.F64

Go's Float64: float64(x << 11 >> 11) / (1 << 53), the low 53 bits

def float_of source · line 243 · raw

@-S:Data -> @p:Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S) -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/f64.F64, S)

def nth source · line 252 · raw

@-A:Data -> @xs:List<&2, A> -> @i:Nat -> Maybe<&2, A>

def put source · line 261 · raw

@-A:Data -> @xs:List<&2, A> -> @i:Nat -> @x:A -> List<&2, A>

def swap_m source · line 270 · raw

@-A:Data -> @xs:List<&2, A> -> @+i:Nat -> @+j:Nat -> @a:Maybe<&2, A> -> @b:Maybe<&2, A> -> List<&2, A>

def swap source · line 278 · raw

@-A:Data -> @+xs:List<&2, A> -> @+i:Nat -> @+j:Nat -> List<&2, A>

exchange elements i and j (unchanged when either is out of range)

def swap_at source · line 281 · raw

@-A:Data -> @-S:Data -> @xs:List<&2, A> -> @+i:Nat -> @p:Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S) -> Pair(List<&2, A>, S)

def len64 source · line 286 · raw

@-A:Data -> @xs:List<&2, A> -> 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64

the length as a 64-bit word

def range_go source · line 311 · raw

@n:Nat -> @acc:List<&2, Nat> -> List<&2, Nat>

def range source · line 319 · raw

@n:Nat -> List<&2, Nat>

[0, 1, ..., n - 1]

Templates

template uint64 source · line 66 · raw

@-S:Data -> @-next:(@_:S -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)) -> @s:S -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)

template uint32 source · line 73 · raw

@-S:Data -> @-next:(@_:S -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)) -> @s:S -> Pair(U32, S)

template int64 source · line 80 · raw

@-S:Data -> @-next:(@_:S -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)) -> @s:S -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)

template int32 source · line 87 · raw

@-S:Data -> @-next:(@_:S -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)) -> @s:S -> Pair(U32, S)

template again source · line 120 · raw

@-S:Data -> @-next:(@_:S -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)) -> @+n:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @+hi:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @+lo:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @s:S -> @reject:Bool -> Draw<S>

one rejection step: while lo < t, draw again; an accepted draw is kept

template step source · line 127 · raw

@-S:Data -> @-next:(@_:S -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)) -> @+n:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @+t:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @d:Draw<S> -> Draw<S>

template retry source · line 133 · raw

@-S:Data -> @-next:(@_:S -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)) -> @fuel:Nat -> @+n:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @+t:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @d:Draw<S> -> Draw<S>

fuel rejection steps (an accepted draw is a fixed point of step)

template lemire_small source · line 147 · raw

@-S:Data -> @-next:(@_:S -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)) -> @+n:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @+hi:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @+lo:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @s:S -> @small:Bool -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)

lo >= n >= t accepts at once; otherwise t = 2^64 mod n is computed and at most 127 more draws are made

template lemire_first source · line 154 · raw

@-S:Data -> @-next:(@_:S -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)) -> @+n:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @d:Draw<S> -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)

template uint64n_pick source · line 159 · raw

@-S:Data -> @-next:(@_:S -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)) -> @s:S -> @+n:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @pow2:Bool -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)

template uint64n source · line 167 · raw

@-S:Data -> @-next:(@_:S -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)) -> @s:S -> @+n:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)

uniform in [0, n) for n > 0 (Go's Uint64N)

template uint_below source · line 170 · raw

@-S:Data -> @-next:(@_:S -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)) -> @s:S -> @+n:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)

template uint32n source · line 178 · raw

@-S:Data -> @-next:(@_:S -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)) -> @s:S -> @+n:U32 -> Pair(U32, S)

uniform in [0, n) for n > 0 (Go's Uint32N)

template intn_z source · line 205 · raw

@-S:Data -> @-next:(@_:S -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)) -> @s:S -> @+n:Nat -> @z:Bool -> Pair(Nat, S)

template intn source · line 213 · raw

@-S:Data -> @-next:(@_:S -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)) -> @s:S -> @+n:Nat -> Pair(Nat, S)

uniform in [0, n) for 0 < n < 2^48 (Go's IntN); (0, s) for n == 0

template int_range source · line 221 · raw

@-S:Data -> @-next:(@_:S -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)) -> @s:S -> @+lo:Nat -> @+hi:Nat -> Pair(Nat, S)

uniform in [lo, hi) for lo < hi, hi - lo < 2^48; (lo, s) when hi <= lo

template float64 source · line 247 · raw

@-S:Data -> @-next:(@_:S -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)) -> @s:S -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/f64.F64, S)

template shuffle_step source · line 294 · raw

@-A:Data -> @-S:Data -> @-next:(@_:S -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)) -> @+i:Nat -> @+n:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @st:Pair(List<&2, A>, S) -> Pair(List<&2, A>, S)

swap element i with a uniform j < n = i + 1

template shuffle_go source · line 299 · raw

@-A:Data -> @-S:Data -> @-next:(@_:S -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)) -> @k:Nat -> @+n:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @st:Pair(List<&2, A>, S) -> Pair(List<&2, A>, S)

i = k, k - 1, ..., 1 with the bound n = i + 1 as a 64-bit word

template shuffle source · line 308 · raw

@-A:Data -> @-S:Data -> @-next:(@_:S -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)) -> @s:S -> @+xs:List<&2, A> -> Pair(List<&2, A>, S)

Go's Shuffle (Fisher-Yates, from the last index down), for fewer than 2^48 elements

template perm source · line 323 · raw

@-S:Data -> @-next:(@_:S -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)) -> @s:S -> @+n:Nat -> Pair(List<&2, Nat>, S)

Go's Perm: a shuffle of 0..n-1