std.rand

Reed's standard library. Imported with use std.rand; not on disk.

Functions

random_seedA generator seeded from a single value.

random_seed #

line 54 
func random_seed(seed: i32) -> &Random

A generator seeded from a single value.

The seed is run through SplitMix64 to fill all four state words, because xorshift128 recovers slowly from a state that is mostly zeros: seeding it with (seed, 0, 0, 0) gives visibly poor output for the first few dozen draws. Every seed, including 0, produces a distinct well-distributed stream.

The same seed always produces the same sequence, on every platform.

Parameters
seed — the starting value
Returns
a new generator
Source 
func random_seed(seed: i32) -> &Random {
  let mixer: &SplitMix = new SplitMix { state: seed as i64.s };
  let a: i64 = mixer.next();
  let b: i64 = mixer.next();
  return new Random {
    x: wasm.i32.wrap_i64(a),
    y: wasm.i32.wrap_i64(a >>> 32),
    z: wasm.i32.wrap_i64(b),
    w: wasm.i32.wrap_i64(b >>> 32),
  };
}

Methods

SplitMix.nextThe next 64 bits of a SplitMix64 stream.
Random.nextThe next 32 pseudorandom bits, uniformly distributed over the whole i32 range.
Random.next_i64The next 64 pseudorandom bits.
Random.belowA uniformly distributed value in 0..bound.
Random.betweenA uniformly distributed value in lo..hi.
Random.booleanA pseudorandom boolean.
Random.unitA pseudorandom f64 in [0, 1).
Random.shuffleShuffles values in place, uniformly.
Random.choiceA uniformly chosen element of values.

SplitMix.next #

line 73 
func SplitMix.next(self: &SplitMix) -> i64

The next 64 bits of a SplitMix64 stream.

A complete generator in its own right, and the standard way to seed a larger one. Each call advances the state by a fixed odd increment and then mixes, so consecutive seeds give unrelated outputs -- the property random_seed needs.

Returns
the next value
Source 
func SplitMix.next(self: &SplitMix) -> i64 {
  self->state = self->state + 0x9E3779B97F4A7C15;
  var z: i64 = self->state;
  z = (z ^ (z >>> 30)) * 0xBF58476D1CE4E5B9;
  z = (z ^ (z >>> 27)) * 0x94D049BB133111EB;
  return z ^ (z >>> 31);
}

Random.next #

line 88 
func Random.next(self: &Random) -> i32

The next 32 pseudorandom bits, uniformly distributed over the whole i32 range.

Every other method here is built on this one. The result is as likely to be negative as positive; use below or between for a bounded value.

Returns
the next value
See also
Random.below, Random.between
Source 
func Random.next(self: &Random) -> i32 {
  let t: i32 = self->x ^ (self->x << 11);
  self->x = self->y;
  self->y = self->z;
  self->z = self->w;
  self->w = (self->w ^ (self->w >>> 19)) ^ (t ^ (t >>> 8));
  return self->w;
}

Random.next_i64 #

line 102 
func Random.next_i64(self: &Random) -> i64

The next 64 pseudorandom bits.

Two 32-bit draws combined, so it advances the generator twice.

Returns
the next value
Source 
func Random.next_i64(self: &Random) -> i64 {
  let hi: i64 = self.next() as i64.u;
  let lo: i64 = self.next() as i64.u;
  return (hi << 32) | lo;
}

Random.below #

line 122 
func Random.below(self: &Random, bound: i32) -> i32

A uniformly distributed value in 0..bound.

Returns 0 when bound is zero or negative rather than trapping.

Uniform, not merely bounded. The naive next() % bound is biased whenever bound does not divide 2^32: the low residues occur once more often than the high ones, by up to a factor of bound / 2^32. This rejects the unbalanced tail of the range instead, so every value in 0..bound is exactly equally likely. The rejection loop is expected to run barely more than once (at most twice on average, and only for a bound above 2^31).

Parameters
bound — the exclusive upper bound
Returns
a value in 0..bound
See also
Random.between
Source 
func Random.below(self: &Random, bound: i32) -> i32 {
  if (bound <= 0) { return 0; }
  // The largest multiple of `bound` that fits in the unsigned 32-bit range; draws at or
  // above it are the biased tail and are rejected.
  //
  // When `bound` divides 2^32 -- every power of two, which `shuffle` hits constantly --
  // that multiple *is* 2^32, which wraps to `0` here. Zero cannot be compared against as a
  // limit (`lt_u(0)` is never true, so the loop below would never terminate), and it also
  // needs no rejection at all: the range divides evenly, so `rem_u` is already uniform.
  let limit: i32 = 0 - ((0 - bound).rem_u(bound));
  if (limit == 0) { return self.next().rem_u(bound); }
  loop draw() {
    let value: i32 = self.next();
    if (value.lt_u(limit)) { return value.rem_u(bound); }
    continue draw();
  }
}

Random.between #

line 150 
func Random.between(self: &Random, lo: i32, hi: i32) -> i32

A uniformly distributed value in lo..hi.

Returns lo when the range is empty. A range spanning more than 2^31 values is handled correctly: the width is computed as unsigned, so between(-2147483648, 2147483647) works rather than overflowing.

Parameters
lo — the inclusive lower bound
hi — the exclusive upper bound
Returns
a value in lo..hi
See also
Random.below
Source 
func Random.between(self: &Random, lo: i32, hi: i32) -> i32 {
  if (hi <= lo) { return lo; }
  return lo + self.below(hi - lo);
}

Random.boolean #

line 161 
func Random.boolean(self: &Random) -> i32

A pseudorandom boolean.

Reads the high bit, not the low one: xorshift's low bits are its weakest, and next() & 1 is a visibly worse coin than next() < 0.

Returns
0 or 1, each with probability one half
Source 
func Random.boolean(self: &Random) -> i32 {
  return (self.next() >>> 31) & 1;
}

Random.unit #

line 172 
func Random.unit(self: &Random) -> f64

A pseudorandom f64 in [0, 1).

Built from 53 random bits, which is exactly the mantissa width of an f64, so every representable value in the interval is reachable and the distribution is uniform. The common next() / 2^32 formulation reaches only 2^32 of them.

Returns
a value in [0, 1)
Source 
func Random.unit(self: &Random) -> f64 {
  let bits: i64 = self.next_i64() >>> 11;
  return (bits as f64.u) * 1.1102230246251565e-16;
}

Random.shuffle #

line 185 
func Random.shuffle(self: &Random, values: &I32Values) -> void

Shuffles values in place, uniformly.

The Fisher-Yates shuffle: every one of the n! orderings is equally likely, assuming the generator is. Note the loop runs downward and picks from 0..=i inclusive -- the common "pick from the whole array each time" variant is not uniform and quietly favours some orderings over others.

Parameters
values — the array to shuffle
Source 
func Random.shuffle(self: &Random, values: &I32Values) {
  var i: i32 = #values;
  loop swap() {
    if (i <= 1) { break swap(); }
    i = i - 1;
    let j: i32 = self.below(i + 1);
    let t: i32 = values[i];
    values[i] = values[j];
    values[j] = t;
    continue swap();
  }
}

Random.choice #

line 205 
func Random.choice(self: &Random, values: &I32Values) -> (i32, i32)

A uniformly chosen element of values.

Returns (0, 0) for an empty array; the flag distinguishes that from having drawn a stored zero.

Parameters
values — the array to choose from
Returns
(value, ok)
Source 
func Random.choice(self: &Random, values: &I32Values) -> (i32, i32) {
  if (#values == 0) { return (0, 0); }
  return (values[self.below(#values)], 1);
}

Types

RandomA xorshift128 pseudorandom generator.
SplitMixA SplitMix64 state, for expanding one seed into many well-distributed values.

Random #

line 31 
struct Random {
  x: mut i32,
  y: mut i32,
  z: mut i32,
  w: mut i32,
}

A xorshift128 pseudorandom generator. Create one with random_seed.

Source 
struct Random {
  x: mut i32,
  y: mut i32,
  z: mut i32,
  w: mut i32,
}

SplitMix #

line 39 
struct SplitMix {
  state: mut i64,
}

A SplitMix64 state, for expanding one seed into many well-distributed values.

Source 
struct SplitMix {
  state: mut i64,
}