# Random numbers

> The random library splits randomness into engines that produce raw bits, distributions that shape them into values, and a seed that decides where an engine starts. Each of those parts has traps, from modulo bias and weak seeding to distributions whose output differs between standard libraries.

- **Source:** C++ Atlas (https://cppatlas.com/topics/random-numbers)
- **Track:** Library utilities
- **Estimated reading time:** 12 minutes
- **ISO C++ clauses:** [rand.eng.mers] (https://eel.is/c++draft/rand.eng.mers), [rand.predef] (https://eel.is/c++draft/rand.predef), [rand.dist.uni.int] (https://eel.is/c++draft/rand.dist.uni.int), [rand.dist.uni.real] (https://eel.is/c++draft/rand.dist.uni.real), [rand.util.canonical] (https://eel.is/c++draft/rand.util.canonical), [alg.random.shuffle] (https://eel.is/c++draft/alg.random.shuffle), [alg.random.sample] (https://eel.is/c++draft/alg.random.sample), [c.math.rand] (https://eel.is/c++draft/c.math.rand)
- **cppreference links:** [Pseudo-random number generation](https://en.cppreference.com/w/cpp/numeric/random), [std::random_device](https://en.cppreference.com/w/cpp/numeric/random/random_device), [std::mersenne_twister_engine](https://en.cppreference.com/w/cpp/numeric/random/mersenne_twister_engine), [std::uniform_int_distribution](https://en.cppreference.com/w/cpp/numeric/random/uniform_int_distribution), [std::uniform_real_distribution](https://en.cppreference.com/w/cpp/numeric/random/uniform_real_distribution), [std::seed_seq](https://en.cppreference.com/w/cpp/numeric/random/seed_seq), [std::generate_canonical](https://en.cppreference.com/w/cpp/numeric/random/generate_canonical), [std::philox_engine](https://en.cppreference.com/w/cpp/numeric/random/philox_engine), [std::rand](https://en.cppreference.com/w/cpp/numeric/random/rand)
- **Prerequisites:** algorithms, concepts-and-constraints, threads-and-jthread

## The one idea

A random number in C++ comes from three separate objects. A **uniform random bit generator** is a source of unsigned integers spread over a fixed range: an engine such as `std::mt19937`, an adaptor over one, or `std::random_device`. A **distribution** such as `uniform_int_distribution` takes bits from a generator and turns them into the values you actually want. A **seed** decides where a pseudo-random engine starts. Everything you can get wrong is about one of these three: the generator is weaker than you assumed, the distribution is not what you think, or the seed has far fewer possibilities than the engine has states.

```cpp
#include <iostream>
#include <random>

int main() {
  std::random_device rd;                         // seed source: slow, called once
  std::mt19937 gen(rd());                        // engine: deterministic given the seed
  std::uniform_int_distribution<int> die(1, 6);  // distribution: closed interval [1, 6]
  for (int i = 0; i < 5; ++i) std::cout << die(gen) << ' ';
}
```

> **Mental model.** An engine is a deterministic state machine. Same seed, same sequence, on every conforming implementation. Randomness in a program comes only from the seed, and the quality of a program's randomness cannot exceed the quality of its seed.

## Why `rand() % n` is wrong

`std::rand` hands out values in `[0, RAND_MAX]`, where `RAND_MAX` is at least 32767, from hidden global state that you seed with `srand`. Its algorithm and quality are left to the implementation. The remainder trick has a second flaw. Unless `RAND_MAX + 1` is a multiple of `n`, some residues occur more often than others. With a range of 32768 and `n = 6`, the numbers are `5461 * 6 + 2`, so results 0 and 1 are slightly more likely than the others. The effect is tiny for small `n` and severe when `n` is a large fraction of the range. Taking low bits of a weak generator can also be worse than the generator itself.

`std::uniform_int_distribution` avoids the bias; implementations typically do this by consuming as many engine outputs as they need and rejecting values that fall in the uneven tail. It also works with engines whose range is not a power of two. Prefer it to any hand-written reduction.

## Engines and adaptors

The standard supplies three families of engines. `linear_congruential_engine` is tiny and fast and has weak statistical properties. `mersenne_twister_engine`, with the aliases `mt19937` and `mt19937_64`, has a large state and long period. `subtract_with_carry_engine` is the third. **Adaptors** wrap an engine and change its output: `discard_block_engine` throws away part of each block, `independent_bits_engine` repacks bits into a chosen width, and `shuffle_order_engine` (as in `knuth_b`) permutes the output order. `std::default_random_engine` is a typedef whose engine is implementation-defined, so it gives you no portability promise.

The predefined engines have a strong guarantee, because their algorithms and default seeds are specified. The standard states that the 10000th invocation of a default-constructed `mt19937` returns 4123659995, and the other predefined engines have the same kind of check value.

```cpp
#include <iostream>
#include <random>

int main() {
  std::mt19937 g;                        // default seed 5489
  for (int i = 1; i < 10000; ++i) g();
  std::cout << g() << '\n';              // 4123659995 on every conforming implementation
}
```

## Seeding

`std::random_device` is meant to produce non-deterministic numbers from the operating system or hardware. The standard permits an implementation to fall back on a pseudo-random engine if no such source exists, in which case every object may produce the same sequence, so on exotic platforms it can fail to be random at all. Its `entropy()` member is an estimate and not a reliable test of this. It is also slow compared with an engine, and on some systems it degrades when called often. Use it to seed an engine, not as the engine.

The usual one-liner `std::mt19937 gen(std::random_device{}())` seeds with a single 32-bit value. The mt19937 state has 19937 bits, but a single-value seed reduces to 32 bits, so there are at most 2^32 reachable sequences, and the engine is not seeded from anything close to its capacity. Seeding with `1ULL << 32` gives the same engine as seeding with 0. To spread more entropy into the state, give the engine a **seed sequence**:

```cpp
#include <array>
#include <cstdint>
#include <random>

std::mt19937 make_engine() {
  std::random_device rd;
  std::array<std::uint32_t, 8> seed_data;
  for (auto& x : seed_data) x = rd();
  std::seed_seq seq(seed_data.begin(), seed_data.end());
  return std::mt19937(seq);              // state filled from 256 bits of seed data
}
```

`seed_seq` scrambles whatever it is given into as many 32-bit words as the engine asks for. It cannot create entropy that was not there, so eight words from a bad `random_device` are still a bad seed.

## Distributions are not portable

Engines are specified exactly; distributions are not. The standard says what distribution a class produces, such as uniform over `[a, b]`, but not which algorithm computes it or how many engine outputs it uses. As a result, the same engine and seed can yield different dice rolls on libstdc++ and libc++, and `std::shuffle` is just as unspecified. The raw engine output is the same everywhere.

If you need reproducible results across platforms, for tests with golden files or for networked simulations, take the engine's raw output and write the mapping yourself, or ship your own distribution implementation. Within one build of one library the sequence is reproducible, but an upgrade of the library may change it.

Distributions can also hold **state**. A normal distribution, for example, commonly produces values in pairs and keeps the spare one. Calling `reset()` discards such cached state, so the next call draws fresh engine output. Copying a distribution copies this state with it. If you want one fixed stream per task, do not share distribution objects between tasks.

## Ranges and types

`uniform_int_distribution<T>(a, b)` is a closed interval: both `a` and `b` can occur. Passing `a > b` violates a precondition and is undefined behavior; nothing swaps the bounds. The type `T` must be one of `short`, `int`, `long`, `long long` or their unsigned versions. The effect of `char`, `signed char`, `unsigned char`, `char8_t`, `wchar_t` or `bool` is undefined. libstdc++ accepts `char`, libc++ rejects it with a `static_assert`, and neither tells you what the standard does. Generate an `int` and cast.

`uniform_real_distribution<T>(a, b)` is **half-open**, `[a, b)`. The mathematics says `b` never appears, but floating-point rounding is a known trouble: the function `generate_canonical`, which underlies it, was specified in a way that let several implementations occasionally return exactly `1.0` for `float`, a defect tracked as LWG 2524. Code that divides by `1 - x` or uses `x` as an array index scaled by the size must not rely on the upper bound being excluded without a guard. A closed real interval is hard to build: using `nextafter(b)` as the upper limit does not always work because of rounding.

`std::generate_canonical<double, 53>(gen)` yields a real in `[0, 1)` using the stated number of bits. It is the building block for most real-valued distributions, and the place the rounding problem comes from.

## Shuffling, sampling, and threads

`std::shuffle(first, last, gen)` permutes a range using a generator. `std::random_shuffle` was deprecated in C++14 and removed in C++17 because it relied on `rand`. `std::sample(first, last, out, n, gen)` (C++17) selects `n` elements without replacement. The result preserves the order of the input only if the input iterators are forward iterators, and which elements are chosen is unspecified in the sense described for distributions: different libraries select differently.

Engines and distributions are ordinary objects with no internal locking. Calling `operator()` on the same object from two threads at once is a data race. Give each thread its own engine, for example a `thread_local` one, and seed each from a seed sequence built from distinct values. Sharing one engine behind a mutex is correct but serializes the threads.

## C++26 additions

C++26 adds `std::philox_engine` with the aliases `philox4x32` and `philox4x64`. This is a **counter-based** engine: its state is small and a position in the sequence can be addressed directly, which suits parallel work where each thread or work item takes its own stream. The aliases have a specified check value for the 10000th output, and GCC 16.2 produces 1955073260 for `philox4x32`, matching it. C++26 also adds `std::ranges::generate_random`, which fills a range with random numbers drawn from a generator, optionally through a distribution. GCC 16.2 does not provide it, so it has not been run for this topic.

## What to remember

- Engine, distribution, and seed are separate; randomness comes only from the seed.
- `rand() % n` is biased unless `n` divides `RAND_MAX + 1`; use `uniform_int_distribution`.
- Predefined engines are fully specified: `mt19937` default-constructed yields 4123659995 on its 10000th call, on every conforming implementation.
- Distributions and `shuffle` are not specified at the algorithm level, so they differ between libraries.
- `uniform_int_distribution` is `[a, b]` and requires `a <= b`; `uniform_real_distribution` is `[a, b)`, with a rounding caveat in `generate_canonical`.
- Only the listed standard integer types work with the integer distributions; `char` and `bool` have undefined effects.
- `random_device` may be deterministic on some platforms and is slow; use it to seed.
- One 32-bit seed reaches at most 2^32 states of `mt19937`; `seed_seq` helps spread seed data but cannot create entropy.
- Do not share an engine or distribution between threads without synchronization.
- `reset()` clears a distribution's cached state; `sample` is stable only with forward iterators.
- C++26 adds `philox_engine` and `ranges::generate_random`.

## Concept Map Outline

- **Random numbers:** Engines produce bits, distributions shape them, and the seed decides the start.
  - **Three parts:** Generator, distribution and seed are separate objects with separate failure modes.
    - **Engines:** Deterministic state machines: same seed gives the same sequence on every implementation.
    - **Adaptors:** discard_block, independent_bits and shuffle_order engines wrap another engine.
    - **Distributions:** Turn engine output into values; the algorithm is not specified, so results vary by library.
    - **Predefined check value:** The 10000th call of a default mt19937 returns 4123659995.
  - **Why not rand():** std::rand has hidden global state and implementation-defined quality.
    - **Modulo bias:** rand() % n favors some residues unless n divides RAND_MAX + 1.
    - **Small RAND_MAX:** RAND_MAX is only guaranteed to be at least 32767.
    - **random_shuffle removed:** It used rand and was removed in C++17; use shuffle with an engine.
  - **Seeding:** A program's randomness cannot exceed its seed's.
    - **random_device:** Meant to be non-deterministic, but may be a fixed pseudo-random engine on some platforms.
    - **Single 32-bit seed:** Reaches at most 2^32 of mt19937's states; 1<<32 and 0 give the same engine.
    - **seed_seq:** Spreads seed words over the engine state but cannot add entropy.
  - **Distribution rules:** Interval conventions and permitted types differ per distribution.
    - **Integer is closed:** uniform_int_distribution gives [a, b] and needs a <= b, else undefined behavior.
    - **Real is half-open:** uniform_real_distribution gives [a, b), but rounding has returned b in some libraries.
    - **Allowed int types:** Only short, int, long, long long and unsigned forms; char and bool are undefined.
    - **State and reset:** Distributions may cache values, as normal does; reset discards the cache.
  - **Algorithms and threads:** Shuffle and sample take a generator, and generators are not thread-safe.
    - **shuffle:** Permutes a range with a generator; results differ between libraries.
    - **sample:** C++17 selection without replacement; stable only for forward iterators.
    - **Thread safety:** Concurrent calls on one engine or distribution race; use one engine per thread.
  - **C++26:** Counter-based generation for parallel work.
    - **philox_engine:** Counter-based engine with philox4x32 and philox4x64 aliases.
    - **generate_random:** Ranges algorithm that fills a range from a generator; not in GCC 16.2.

## Standardese Quiz Questions

### Question 1 [warmup] ([rand.dist.uni.int])

What does this program print?

```cpp
#include <iostream>
#include <random>

int main() {
  std::uniform_int_distribution<int> d(1, 6);
  std::cout << d.min() << ' ' << d.max() << '\n';
}
```

A. `1 5`
B. `0 6`
C. `1 7`
D. `1 6`

**Answer (D):** `1 6`

**Why:** `uniform_int_distribution` produces values on the closed interval `[a, b]`, so both bounds can occur and `max()` is 6. The half-open convention belongs to `uniform_real_distribution`, and carrying it over to integers is the usual off-by-one.

### Question 2 [warmup] ([rand.eng.mers])

What does this program print?

```cpp
#include <iostream>
#include <random>

int roll() {
  std::mt19937 gen(42);
  std::uniform_int_distribution<int> d(1, 6);
  return d(gen);
}

int main() {
  std::cout << (roll() == roll()) << '\n';
}
```

A. `1`
B. `0`
C. Unspecified: it depends on the platform's clock
D. Undefined behavior

**Answer (A):** `1`

**Why:** Each call builds a new engine from the same seed and a new distribution in the same initial state, so both calls compute exactly the same value. An engine is a deterministic function of its state. Creating the engine inside a frequently called function is a common cause of a random generator that always returns the same number.

### Question 3 [warmup] ([c.math.rand])

Assume `RAND_MAX` is 32767 and `rand()` returns each value in `[0, 32767]` exactly once per 32768 draws. Which results of `rand() % 6` come up more often than the others?

A. None: each result is equally likely
B. `0` and `1`
C. `4` and `5`
D. `0` only

**Answer (B):** `0` and `1`

**Why:** There are 32768 inputs and 6 results, and 32768 = 6 * 5461 + 2. The inputs 0 to 32765 split evenly, and the two left-over inputs, 32766 and 32767, map to results 0 and 1. Those two results each occur 5462 times against 5461 for the rest. The bias is small here but grows as the modulus approaches the range, which is why `uniform_int_distribution` rejects or rescales instead of taking a remainder.

### Question 4 [tricky] ([rand.eng.mers], [rand.dist.uni.int], [alg.random.shuffle])

The program below runs on two conforming implementations, each with a different standard library. Which of the lines are guaranteed to print the same values on both?

```cpp
#include <algorithm>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>

int main() {
  std::mt19937 e1(42);
  std::cout << e1() << '\n';                       // line 1

  std::mt19937 e2(42);
  std::uniform_int_distribution<int> d(1, 6);
  std::cout << d(e2) << '\n';                      // line 2

  std::mt19937 e3(42);
  std::vector<int> v(10);
  std::iota(v.begin(), v.end(), 0);
  std::shuffle(v.begin(), v.end(), e3);
  std::cout << v[0] << '\n';                       // line 3
}
```

A. Only line 1
B. Lines 1 and 2
C. Lines 1 and 3
D. All three lines

**Answer (A):** Only line 1

**Why:** The standard defines the algorithm of `mt19937`, including seeding from a single value, so its raw output is the same everywhere. It does not define how a distribution turns engine output into a value or how `shuffle` consumes it, so lines 2 and 3 can differ between libraries. They do differ between libstdc++ and libc++ for this seed.

### Question 5 [tricky] ([rand.eng.mers])

What does this program print?

```cpp
#include <iostream>
#include <random>

int main() {
  std::mt19937 a(1ULL << 32);
  std::mt19937 b(0);
  std::cout << (a() == b()) << '\n';
}
```

A. `0`: the seeds are different, so the sequences differ
B. `1`
C. Unspecified
D. Ill-formed: the seed does not fit in `result_type`

**Answer (B):** `1`

**Why:** The single-value seed is reduced modulo 2^32 for `mt19937`, so `1 << 32` and `0` give the same state. Where `result_type` is 32 bits wide, the conversion of the argument already truncates it, and where it is wider the engine's own reduction does the same. The call is not ill-formed, since an integer converts implicitly. A 32-bit seed can select at most 2^32 of the engine's possible states.

### Question 6 [tricky] ([rand.dist.uni.int])

What does the C++ standard say about this program?

```cpp
#include <iostream>
#include <random>

int main() {
  std::mt19937 gen(1);
  std::uniform_int_distribution<int> d(6, 1);
  std::cout << d(gen) << '\n';
}
```

A. It prints an integer in `[1, 6]`, because the bounds are swapped
B. It throws `std::invalid_argument`
C. The program is ill-formed
D. Undefined behavior: `a <= b` is a precondition

**Answer (D):** Undefined behavior: `a <= b` is a precondition

**Why:** The distribution requires `a <= b`, and the constructor does not check or reorder its arguments. Violating a precondition is undefined behavior, so nothing in the standard promises the swapped range, an exception, or a diagnostic. Some implementations happen to produce numbers in the swapped range, which is exactly why the bug survives testing.

### Question 7 [standardese] ([rand.predef], [rand.eng.mers])

In C++23, what does this program print?

```cpp
#include <iostream>
#include <random>

int main() {
  std::mt19937 g;
  for (int i = 1; i < 10000; ++i) g();
  std::cout << g() << '\n';
}
```

A. `4123659995`
B. `3499211612`
C. Unspecified: the default seed is implementation-defined
D. `1043618065`

**Answer (A):** `4123659995`

**Why:** The standard fixes the default seed of `mt19937` at 5489 and requires the 10000th consecutive invocation of a default-constructed engine to produce 4123659995. The loop makes 9999 calls and the next one is the 10000th. The value 3499211612 is the first output of the default engine, and 1043618065 is the corresponding value for `minstd_rand0`.

### Question 8 [standardese] ([rand.dist.uni.int])

What does the C++23 standard say about instantiating `std::uniform_int_distribution<char>`?

```cpp
#include <random>

int main() {
  std::mt19937 g;
  std::uniform_int_distribution<char> d('a', 'z');
  (void)d(g);
}
```

A. It is well-formed and produces `char` values in `['a', 'z']`
B. The effect is undefined, because only the listed standard integer types other than the character types and `bool` are permitted
C. It is ill-formed, and every conforming compiler must reject it
D. It is implementation-defined, and each library must document its behavior

**Answer (B):** The effect is undefined, because only the listed standard integer types other than the character types and `bool` are permitted

**Why:** The distribution templates are defined only for the types `short`, `int`, `long`, `long long` and their unsigned counterparts; the effect of using any other type, including `char`, `bool` and the sized aliases for char types, is undefined. Libraries may reject it, as libc++ does with a `static_assert`, or accept it, as libstdc++ does, but neither is required. Use `int` and convert the result.
