Reference

std/random/lib

std/random/src/lib.trb

Random, a seedable, splittable generator of random numbers that is a value: the same seed makes the same numbers on every machine and in both back ends, and a generator handed to a function is how that function gets its randomness (docs/design/RANDOM.md).

The algorithm is SplitMix64, and it is a promise: the sequence of a seed, the mapping from its bits to integers and floats, the shuffle and the split are documented, frozen and pinned by known-answer tests, so numbers recorded with one version of the toolchain are the numbers of every later one. Ordinary TorbScript over UInt64 and its wrapping arithmetic, with no native and no capability: a package that makes random values from a generator it was handed needs no permission. The operating system's source of unpredictable bytes is Entropy of std/os/entropy, and its Entropy.int64() is where a seed that nobody can repeat comes from: Random.seeded Entropy.int64().

Not for secrets. SplitMix64 is fast and passes the statistical batteries, and a generator that is seeded with 64 bits can be recovered from a few of its outputs. A key, a nonce or a token is made from Entropy.

Examples

var source = Random.seeded 42
const roll = source.int(1..=6)
print "{roll}"

var again = Random.seeded 42
print(again.int(1..=6) == roll)
// prints true

Related

type Random

type Random

A pseudo-random generator: SplitMix64, a 64-bit state that advances by an odd increment, its gamma, on every draw and is mixed into the number the draw answers. Two generators with the same state and gamma make the same numbers, which is the point; a copy of a generator repeats the numbers of the original, so a var is what draws.

A generator is made from a seed with Random.seeded, and a part of a computation that needs numbers of its own gets one from Random.split instead of sharing: the numbers then do not depend on the order the parts run in.

Examples

var source = Random.seeded 7
const first = source.uint64()
var copy = source
print(copy.uint64() == source.uint64())
// prints true
print(first != source.uint64())
// prints true

Pitfalls

  • Not for cryptography; see the module comment.
  • Drawing changes the generator, so the receiver has to be a var: var source = Random.seeded 42.

Related

fn seeded

static fn seeded(seed: Int): Self

The generator of seed: the state is the seed's 64 bits (the two's complement of a negative seed) and the gamma is the golden gamma, 0x9e3779b97f4a7c15. The same seed makes the same sequence on every machine.

Examples

var source = Random.seeded 1234567
print source.uint64()
// prints 6457827717110365317

fn uint64

var fn uint64(): UInt64

The next 64 random bits as a UInt64, the output of SplitMix64 and the source of every other draw: the state advances by the gamma, and the new state goes through the mixing function of the reference implementation (z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9, z = (z ^ (z >> 27)) * 0x94d049bb133111eb, z ^ (z >> 31)). The sequence of Random.seeded 1234567 begins 6457827717110365317, 3203168211198807973, 9817491932198370423.

Examples

var source = Random.seeded 0
print source.uint64()
// prints 16294208416658607535

fn float

var fn float(): Float64

A float in [0, 1): the top 53 bits of Random.uint64 (uint64() >> 11) divided by 2^53. Every answer is a multiple of 2^-53, each of them equally likely, and the answer is never 1.0.

Examples

var source = Random.seeded 42
const chance = source.float()
print(chance >= 0.0 && chance < 1.0)
// prints true

fn int

var fn int(range: Range<Int>): Int

A whole number of range, every one equally likely: source.int(1..=6) is a die and source.int(0..items.length()) an index. The draw is unbiased - it rejects the outputs of Random.uint64 that would make some numbers likelier than others instead of taking a remainder of all of them: with count numbers in the range and limit the remainder of 2^64 divided by count, the first output of at least limit answers range.start plus its remainder by count. A range that covers all 2^64 numbers answers range.start plus an output.

Examples

var source = Random.seeded 42
const die = source.int(1..=6)
print(die >= 1 && die <= 6)
// prints true

Panics

Where the range holds no number: 5..5, or 6..=5. A range of one number is fine, and answers it.

fn split

var fn split(): Self

A generator of its own, independent of this one for any practical purpose: it takes the next output as its state and a gamma mixed from the following state, and this generator moves on by two draws. Hand a split to each part of a parallel computation, and the numbers of every part stay the same whichever part runs first.

The gamma is the one of Java's SplittableRandom: the state mixed by MurmurHash3's finalizer, made odd, and flipped by 0xaaaaaaaaaaaaaaaa when it has fewer than 24 bit transitions, so that it is not a weak increment. That two splits are independent is an empirical statement, as it is for every splittable generator of this family.

Examples

var source = Random.seeded 42
var left = source.split()
var right = source.split()
print(left.uint64() != right.uint64())
// prints true

fn shuffled

var fn shuffled<Item>(items: List<Item>): List<Item>

The items in a random order, the original untouched. The order is Fisher-Yates from the end: for each position index from the last down to 1, source.int(0..=index) picks the item that swaps into it.

Examples

var source = Random.seeded 42
const order = source.shuffled([1, 2, 3, 4, 5])
print order.length()
// prints 5
print(source.float() < 1.0)
// prints true

fn shuffle

var fn shuffle<Item>(var items: List<Item>)

Puts items in a random order, in place, with the Fisher-Yates shuffle of Random.shuffled.

Examples

var source = Random.seeded 42
var cards = ["ace", "king", "queen"]
source.shuffle cards
print cards.length()
// prints 3
print(source.choice(cards) != None)
// prints true

fn choice

var fn choice<Item>(items: List<Item>): Item?

One item of items, every one equally likely, or None where there is none: the item at int(0..items.length()).

Examples

var source = Random.seeded 42
const nobody: List<String> = []
print(source.choice(nobody) == None)
// prints true
print(source.choice(["only"]) == Some("only"))
// prints true

fn sample

var fn sample<Item>(items: List<Item>, count: Int): List<Item>

count different positions of items and the items at them, in a random order: the first count positions of a shuffle that stops early. For each position index from 0 up to count, source.int(index..items.length()) picks the item that swaps into it. A sample of every item is a shuffle, and an item that is in items twice can be in the sample twice.

Examples

var source = Random.seeded 42
const hand = source.sample([1, 2, 3, 4, 5], 2)
print hand.length()
// prints 2

Panics

Where count is negative or more than items.length(): there are not that many different items to take.