Генерация псевдослучайных чисел

Библиотека генерации случайных чисел предоставляет классы для генерации случайных и псевдослучайных чисел. К ним относятся:

• Равномерные генераторы случайных битов (URBG), включая движки случайных чисел — генераторы псевдослучайных чисел, создающие целочисленные последовательности с равномерным распределением, — и генераторы истинно случайных чисел (если доступны).
• Распределения случайных чисел (например, равномерное, нормальное или распределение Пуассона), преобразующие выходные данные URBG в различные статистические распределения.

URBG и распределения предназначены для совместного использования при получении случайных значений. Все движки случайных чисел можно явно инициализировать начальными данными, сериализовать и десериализовать для использования в воспроизводимых симуляторах.

Равномерные генераторы случайных битов

Равномерный генератор случайных битов — это функциональный объект, возвращающий беззнаковые целочисленные значения, причём каждое значение из диапазона возможных результатов (в идеале) имеет одинаковую вероятность возврата.

Все равномерные генераторы случайных битов соответствуют требованиям UniformRandomBitGenerator. В C++20 также определено понятие uniform_random_bit_generator.

Движки случайных чисел

Движок случайных чисел (обычно сокращённо движок ) — это равномерный генератор случайных битов, создающий псевдослучайные числа с использованием начальных данных в качестве источника энтропии.

В любой момент времени движок e типа E имеет состояние ei для некоторого неотрицательного целого числа i. При создании e имеет начальное состояние e0, определяемое параметрами движка и начальным значением (или последовательностью начальных значений).

Для любого типа движка E всегда определены следующие свойства:

• Размер состояния E в единицах размера E::result_type (то есть (sizeof ei) / sizeof(E::result_type)).
• Алгоритм перехода TA, с помощью которого состояние e ei переходит в следующее состояние ei+1 (то есть TA(ei) == ei+1).
• Алгоритм генерации GA, с помощью которого состояние e отображается в значение типа E::result_type; результатом является псевдослучайное число.

Последовательность псевдослучайных чисел можно сгенерировать, попеременно вызывая TA и GA.

Стандартная библиотека предоставляет реализации трёх различных классов алгоритмов генерации псевдослучайных чисел в виде шаблонов классов, что позволяет настраивать алгоритмы. Выбор движка связан с рядом компромиссов:

• Линейный конгруэнтный движок работает с умеренной скоростью и требует очень мало памяти для хранения состояния.
• Движок вихря Мерсенна работает медленнее и требует больше памяти для хранения состояния, но при правильном выборе параметров обеспечивает самую длинную неповторяющуюся последовательность с наиболее желательными спектральными характеристиками (при заданном определении желательных характеристик).
• Движок вычитания с заёмом работает очень быстро даже на процессорах без расширенных наборов арифметических инструкций, но требует больше памяти для хранения состояния и иногда обладает менее желательными спектральными характеристиками.

Ни один из этих движков случайных чисел не является криптографически стойким. Как и для любой защищённой операции, для этих целей следует использовать криптографическую библиотеку (например, OpenSSL RAND_bytes).

Все типы, созданные на основе этих шаблонов, соответствуют требованиям RandomNumberEngine.

Адаптеры движков случайных чисел

Адаптеры движков случайных чисел генерируют псевдослучайные числа, используя другой движок случайных чисел в качестве источника энтропии. Обычно они применяются для изменения спектральных характеристик базового движка.

Предопределённые генераторы случайных чисел

Предопределено несколько популярных алгоритмов.

Недетерминированные случайные числа

std::random_device — это недетерминированный равномерный генератор случайных битов, хотя реализациям разрешено реализовывать std::random_device с помощью движка псевдослучайных чисел, если поддержка генерации недетерминированных случайных чисел отсутствует.

Распределения случайных чисел

Распределение случайных чисел выполняет постобработку выходных данных URBG таким образом, чтобы результирующие данные соответствовали заданной статистической функции плотности вероятности.

Распределения случайных чисел соответствуют требованиям RandomNumberDistribution.

Утилиты

Алгоритмы генерации случайных чисел

Библиотека случайных чисел C

Помимо описанных выше генераторов и распределений, доступны также функции и константы из библиотеки случайных чисел C, хотя их использование не рекомендуется:

Пример

#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <random>
#include <string>

int main()
{
    // Seed with a real random value, if available
    std::random_device r;
    
    // Choose a random mean between 1 and 6
    std::default_random_engine e1(r());
    std::uniform_int_distribution<int> uniform_dist(1, 6);
    int mean = uniform_dist(e1);
    std::cout << "Randomly-chosen mean: " << mean << '\n';
    
    // Generate a normal distribution around that mean
    std::seed_seq seed2{r(), r(), r(), r(), r(), r(), r(), r()};
    std::mt19937 e2(seed2);
    std::normal_distribution<> normal_dist(mean, 2);
    
    std::map<int, int> hist;
    for (int n = 0; n != 10000; ++n)
        ++hist[std::round(normal_dist(e2))];
    
    std::cout << "Normal distribution around " << mean << ":\n"
              << std::fixed << std::setprecision(1);
    for (auto [x, y] : hist)
        std::cout << std::setw(2) << x << ' ' << std::string(y / 200, '*') << '\n';
}

Randomly-chosen mean: 4
Normal distribution around 4:
-4
-3
-2
-1
 0 *
 1 ***
 2 ******
 3 ********
 4 *********
 5 ********
 6 ******
 7 ***
 8 *
 9
10
11
12

См. также