random.bend relies on unsafe/foreign

raw source on the hub · import bend-kit-random@0.1.0.1/random.bend as Random

Seeded pseudo-random numbers: xoshiro128**, unbiased ranges, floats and shuffles. Not for cryptography.

1 import

import Base

Types

type Rng source · line 9 · raw

Data

xoshiro128** state (https://prng.di.unimi.it/xoshiro128starstar.c). It is never all zero.

Rng

@a:U32 -> @b:U32 -> @c:U32 -> @d:U32 -> Rng

Definitions

def rotl source · line 12 · raw

@+x:U32 -> @l:Nat -> @r:Nat -> U32

def mix source · line 16 · raw

@+z:U32 -> U32

splitmix32's output mixer, a bijection on U32.

def seed source · line 22 · raw

@+s:U32 -> Rng

The first four splitmix32 outputs from s. Distinct seeds give distinct states.

def from_state.if source · line 26 · raw

@zero:Bool -> @a:U32 -> @b:U32 -> @c:U32 -> @d:U32 -> Rng

def from_state source · line 34 · raw

@+a:U32 -> @+b:U32 -> @+c:U32 -> @+d:U32 -> Rng

The state (a, b, c, d) as is, to replay a reference stream. All zero gives seed(0).

def next source · line 38 · raw

@r:Rng -> Pair(U32, Rng)

One xoshiro128** step: a uniform U32 and the next state.

def Bool.case source · line 47 · raw

@-A:Type -> @b:Bool -> @t:(@_:Unit -> A) -> @f:(@_:Unit -> A) -> A

def below.go source · line 55 · raw

@fuel:Nat -> @+n:U32 -> @+t:U32 -> @xr:Pair(U32, Rng) -> Pair(U32, Rng)

Rejects draws below t = 2^32 mod n, as OpenBSD's arc4random_uniform does.

def below.if source · line 66 · raw

@small:Bool -> @+n:U32 -> @r:Rng -> Pair(U32, Rng)

def below source · line 75 · raw

@+n:U32 -> @r:Rng -> Pair(U32, Rng)

A uniform U32 in [0, n). Each draw is rejected with odds under 1/2, so after 64 rejections, odds 2^-64, it takes x mod n. For n < 2 it is 0 and r is unchanged.

def range.fin source · line 78 · raw

@lo:U32 -> @xr:Pair(U32, Rng) -> Pair(U32, Rng)

def range source · line 83 · raw

@+lo:U32 -> @hi:U32 -> @r:Rng -> Pair(U32, Rng)

A uniform U32 in [lo, hi). For hi <= lo + 1 it is lo and r is unchanged.

def unit.fin source · line 86 · raw

@xr:Pair(U32, Rng) -> Pair(F32, Rng)

def unit source · line 91 · raw

@r:Rng -> Pair(F32, Rng)

A uniform F32 in [0, 1), from the draw's top 24 bits.

def from_os.fin source · line 156 · raw

@e:Result<&1, &1, Pair(U32, String), Pair(U32, Pair(U32, Pair(U32, U32)))> -> Result<&1, &1, Pair(U32, String), Rng>

def from_os source · line 165 · raw

IO(Result<&1, &1, Pair(U32, String), Rng>)

A generator seeded from OS entropy, for when runs need not repeat.

Templates

template shuffle.fill source · line 94 · raw

@-T:Data -> @xs:List<&2, T> -> @+i:U32 -> @a:Array<T> -> Array<T>

template shuffle.swap.set source · line 101 · raw

@-T:Data -> @+i:U32 -> @+j:U32 -> @xi:T -> @ax:Pair(Array<T>, T) -> Array<T>

template shuffle.swap source · line 105 · raw

@-T:Data -> @+i:U32 -> @+j:U32 -> @ax:Pair(Array<T>, T) -> Array<T>

template shuffle.go source · line 111 · raw

@-T:Data -> @k:Nat -> @+i:U32 -> @a:Array<T> -> @jr:Pair(U32, Rng) -> Pair(Array<T>, Rng)

Fisher-Yates: at slot i, jr is below(i + 1); slot i swaps with slot j. At k = 0, i is 0 and below(1) drew nothing.

template shuffle.read source · line 122 · raw

@-T:Data -> @k:Nat -> @ax:Pair(Array<T>, T) -> @acc:List<&2, T> -> List<&2, T>

Slots [0, k] of the array, with ax the read of slot k, prepended to acc.

template shuffle.fin source · line 131 · raw

@-T:Data -> @+m:U32 -> @ar:Pair(Array<T>, Rng) -> Pair(List<&2, T>, Rng)

template shuffle.run source · line 135 · raw

@-T:Data -> @+h:T -> @+xs:List<&2, T> -> @r:Rng -> Pair(List<&2, T>, Rng)

template shuffle source · line 144 · raw

@-T:Data -> @xs:List<&2, T> -> @r:Rng -> Pair(List<&2, T>, Rng)

A uniform permutation of xs. Every draw is below(i + 1), so a list of n items uses n - 1 draws.

Effects (foreign code)

effect entropy source · line 152 · raw

IO(Result<&1, &1, Pair(U32, String), Pair(U32, Pair(U32, Pair(U32, U32)))>)

16 bytes from the OS (getentropy, or crypto.getRandomValues in JS).

foreign: effs/random.c, effs/random.js