Random numbers

A random number generator is a function with state: it takes a seed, produces a value and keeps enough state for the next call. The standard library has none, because a program that needs randomness needs a decision about where the seed comes from, and the rand crate is the answer most programs use.

This lesson writes a generator of its own to show the mechanism, maps it onto a range without bias, shuffles a vector with it, and then does the same with the rand crate at version 0.10.3. The last section is the panic for a range that contains nothing.

A seeded generator

A linear congruential generator multiplies the state, adds a constant and takes the high bits as the result. The constants below are the ones the C libraries use, and the high bits are taken because the low ones are the least random.

The program creates a generator with the seed forty-two and prints five values. The same seed gives the same five numbers on every run and on every machine.

struct Lcg { state: u64, } impl Lcg { fn new(seed: u64) -> Self { Lcg { state: seed } } fn next_u32(&mut self) -> u32 { self.state = self .state .wrapping_mul(6_364_136_223_846_793_005) .wrapping_add(1_442_695_040_888_963_407); (self.state >> 33) as u32 } } fn main() { let mut generator = Lcg::new(42); let values: Vec<u32> = (0..5).map(|_| generator.next_u32()).collect(); println!("{values:?}"); }

rustc --edition 2024 lcg.rs
./lcg

[1220265334, 484179026, 886563538, 1353769503, 1460606294]

The numbers look random and are not: five outputs are enough to recover the state and predict the rest, which is why this generator is for a game or a test and not for a password. A seed from the clock is what a real program uses when reproducibility is not wanted, and a fixed seed is what a test uses so that the failure can be repeated.

A number in a range

A die roll needs a number from one to six, and taking the raw value modulo six favours the low numbers slightly, because 2^32 is not a multiple of six. The fix is rejection sampling: compute the largest multiple of six that fits, draw again when the value is above it, and divide.

The program rolls six times with a seed of seven. The values are between one and six, and the same seed gives the same six rolls.

struct Lcg { state: u64, } impl Lcg { fn new(seed: u64) -> Self { Lcg { state: seed } } fn next_u32(&mut self) -> u32 { self.state = self .state .wrapping_mul(6_364_136_223_846_793_005) .wrapping_add(1_442_695_040_888_963_407); (self.state >> 33) as u32 } } fn range(generator: &mut Lcg, low: u32, high: u32) -> u32 { let span = high - low + 1; let limit = u32::MAX - (u32::MAX % span); loop { let value = generator.next_u32(); if value < limit { return low + value % span; } } } fn main() { let mut generator = Lcg::new(7); let rolls: Vec<u32> = (0..6).map(|_| range(&mut generator, 1, 6)).collect(); println!("{rolls:?}"); }

rustc --edition 2024 range.rs
./range

[3, 6, 4, 6, 2, 6]

The rejected values are rare — about one in 700 million for a span of six — so the loop almost always returns on the first try. The modulo is still there, but on a population that is an exact multiple of the span, which is what removes the bias.

Shuffling

A shuffle is a loop over the vector from the end: pick a random index up to the current one and swap. Every permutation is equally likely, and the loop touches each element once, which is why it is the algorithm every library uses.

The program shuffles one to five with a seed of 2024. The order is fixed by the seed, and the multiset is the same five numbers.

struct Lcg { state: u64, } impl Lcg { fn new(seed: u64) -> Self { Lcg { state: seed } } fn next_u32(&mut self) -> u32 { self.state = self .state .wrapping_mul(6_364_136_223_846_793_005) .wrapping_add(1_442_695_040_888_963_407); (self.state >> 33) as u32 } } fn shuffle(values: &mut [u32], generator: &mut Lcg) { for index in (1..values.len()).rev() { let pick = (generator.next_u32() as usize) % (index + 1); values.swap(index, pick); } } fn main() { let mut values = vec![1, 2, 3, 4, 5]; let mut generator = Lcg::new(2024); shuffle(&mut values, &mut generator); println!("{values:?}"); }

rustc --edition 2024 shuffle.rs
./shuffle

[1, 2, 4, 5, 3]

The result is one permutation and not a sorted list, and the same seed reproduces it. A shuffle of a deck uses the same loop, and the only difference is the size of the vector and the quality of the generator.

The rand crate

The rand crate at version 0.10.3 brings the generators, the distributions and the seeding a program needs. StdRng is the standard generator, seed_from_u64 makes it reproducible and random_range produces a number in a range without the bias of the manual version.

The package adds the dependency and rolls five times with a seed. The trait that provides the method is RngExt, which has to be in scope.

cargo new --vcs none dice
cargo add rand@0.10.3
cargo run

[package]
name = "dice"
version = "0.1.0"
edition = "2024"

[dependencies]
rand = "0.10.3"

use rand::rngs::StdRng; use rand::{RngExt, SeedableRng}; fn main() { let mut rng = StdRng::seed_from_u64(42); let rolls: Vec<u32> = (0..5).map(|_| rng.random_range(1..=6)).collect(); println!("{rolls:?}"); }

   Compiling rand_core v0.10.0
   Compiling rand v0.10.3
   Compiling dice v0.1.0 (/tmp/rw8/L105/dice)
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 3.41s
     Running `target/debug/dice`
[1, 4, 2, 4, 6]

The crate pulled eight packages into the lock file, which is the cost of a dependency that has to be correct on every platform. The five rolls are not the five of the manual generator, because the algorithm is different; the seed still makes them reproducible. The lesson on dependencies is the version requirement in the manifest.

A range that is empty

A range with the high end below the low end contains no numbers, and the manual function divides by a span that wrapped around to a huge number or zero. In debug builds the subtraction panics, and that is the first thing a caller sees.

The program asks for a range from six down to one with the same function. The span is 1 - 6 + 1, which underflows a u32.

struct Lcg { state: u64, } impl Lcg { fn new(seed: u64) -> Self { Lcg { state: seed } } fn next_u32(&mut self) -> u32 { self.state = self .state .wrapping_mul(6_364_136_223_846_793_005) .wrapping_add(1_442_695_040_888_963_407); (self.state >> 33) as u32 } } fn range(generator: &mut Lcg, low: u32, high: u32) -> u32 { let span = high - low + 1; let limit = u32::MAX - (u32::MAX % span); loop { let value = generator.next_u32(); if value < limit { return low + value % span; } } } fn main() { let mut generator = Lcg::new(1); println!("{}", range(&mut generator, 6, 1)); }

rustc --edition 2024 empty.rs
./empty


thread 'main' (5215) panicked at empty.rs:20:16:
attempt to subtract with overflow
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

The panic names the line of the subtraction, and the thread id changes on every run. A release build wraps instead and returns a value nobody asked for, which is worse; the fix is to reject the arguments before the arithmetic, and the rand crate panics with a message that says the range is empty. The next lesson recognises text instead of numbers.

Exercises

  1. Draw a card from a deck of fifty-two with the manual range function and print its suit and rank.
  2. Run the seeded generator twice with the same seed and check that both sequences are equal.
  3. Replace the generator of the shuffle with StdRng and confirm that the crate produces a different permutation for the same seed.

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What makes a pseudo-random sequence reproducible?

    Answer

    The same seed

    The generator is a function of its state, and the seed is the initial state.

  2. Why is a raw value taken modulo six slightly biased?

    Answer

    The range of the generator is not a multiple of six

    A few of the possible values map to the low results more often than the rest.

  3. What does rejection sampling do?

    Answer

    Draws again when the value falls outside the largest exact multiple

    Dropping the uneven tail leaves a population where the modulo is exact.

  4. Why does a shuffle start at the end of the vector?

    Answer

    Each element is swapped with one at or before it, so every permutation is equally likely

    The Fisher-Yates loop gives each permutation the same probability with one pass.

  5. What does this program print? struct Lcg { state: u64, } impl Lcg { fn next(&mut self) -> u64 { self.state = self.state.wrapping_mul(6_364_136_223_846_793_005).wrapping_add(1); self.state >> 33 } } fn main() { let mut first = Lcg { state: 9 }; let mut second = Lcg { state: 9 }; println!("{}", first.next() == second.next()); }

    Answer

    true

    Two generators with the same seed produce the same first value.

  6. What does this program print? fn main() { let values: Vec<u32> = (0..5).map(|value| value % 3).collect(); println!("{values:?}"); }

    Answer

    [0, 1, 2, 0, 1]

    The remainder cycles through zero, one and two.

  7. What does this program print? fn main() { let mut values = vec![1, 2, 3]; let last = values.len() - 1; values.swap(0, last); println!("{values:?}"); }

    Answer

    [3, 2, 1]

    Swapping the first and last elements reverses this three-element vector.

  8. What does this program print? fn main() { let limit: u32 = u32::MAX - (u32::MAX % 6); println!("{}", limit % 6); }

    Answer

    0

    The limit is the largest multiple of six that fits, so it divides exactly.

  9. What does this program print? fn main() { let low: u32 = 6; let high: u32 = 1; println!("{:?}", high.checked_sub(low)); }

    Answer

    None

    The checked subtraction reports that the result does not fit instead of wrapping.

  10. What does this program print? fn main() { let state: u64 = 42; let next = state.wrapping_mul(6_364_136_223_846_793_005); println!("{}", next > 0); }

    Answer

    true

    The wrapping multiplication is defined and leaves a value above zero.

The code on this page was built with rustc 1.96.1 and cargo 1.96.1, with rand 0.10.3 from crates.io, and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev