Pseudo-random number generation

Библиотека случайных чисел предоставляет классы, генерирующие случайные и псевдослучайные числа. Эти классы включают:

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

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

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

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

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

Генераторы случайных чисел

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Утилиты

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

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

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

Пример

#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <random>
#include <string>
int main()
{
    // Инициализация генератора случайным значением, если доступно
    std::random_device r;
    // Выбор случайного среднего значения между 1 и 6
    std::default_random_engine e1(r());
    std::uniform_int_distribution<int> uniform_dist(1, 6);
    int mean = uniform_dist(e1);
    std::cout << "Случайно выбранное среднее: " << mean << '\n';
    // Генерация нормального распределения вокруг этого среднего
    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 << "Нормальное распределение вокруг " << mean << ":\n"
              << std::fixed << std::setprecision(1);
    for (auto [x, y] : hist)
        std::cout << std::setw(2) << x << ' ' << std::string(y / 200, '*') << '\n';
}

Случайно выбранное среднее: 4
Нормальное распределение вокруг 4:
-4
-3
-2
-1
 0 *
 1 ***
 2 ******
 3 ********
 4 *********
 5 ********
 6 ******
 7 ***
 8 *
 9
10
11
12

Смотрите также