Как генерировать случайные числа

В стандартной библиотеке есть большое количество случайных распределений, которые предполагается использовать совместно с некоторым генератором случайных чисел.
Какой из генераторов в каких случаях следует использовать, и если это псевдослучайный генератор - то как его инициализировать?

Ответ

Генераторы псевдослучайных чисел
В стандартной библиотеке есть три генератора псевдослучайных чисел (ГПСЧ, англ. PRNG) и один почти (sic!) генератор случайных чисел - random_device
linear_congruential_engine, линейный конгруэнтный генератор - самый простой, быстрый и низкокачественный. Использует формулу x[i] = x[i - 1] * A + B. Эквивалентен функции rand(). Внутреннее состояние - это одно случайное число, совершенно предсказуем.
subtract_with_carry_engine, запаздывающий генератор Фибоначчи - немного лучше линейного конгруэнтного генератора, имеет состояние в несколько случайных чисел.
mersenne_twister_engine, Вихрь Мерсена - наиболее качественная выдача случайных чисел с практически бесконечным периодом, большое состояние - 624 числа (2.5 Кб).
Рекомендуемый ГПСЧ - это std::mt19937 - один из вариантов Вихря Мерсена.
Все ГПСЧ являются детерминированными, поэтому для того чтобы выдача не повторялась, их состояние надо инициализировать какой-то уникальной последовательностью чисел. Для этого можно использовать текущее время, чем точнее - тем лучше, например:
auto now = std::chrono::high_resolution_clock::now(); std::mt19937 random_generator(now.time_since_epoch().count());
В некоторых случаях может оказаться что текущего времени не достаточно, и нужен дополнительный источник энтропии. Для этого можно использовать утилиту seed_seq, которая выравнивает данные нескольких источников энтропии:
auto now1 = (uint64_t)std::chrono::high_resolution_clock::now().time_since_epoch().count(); uint64_t thread_id = std::hash{}(std::this_thread::get_id()); std::random_device random_device; uint64_t entropy = random_device(); auto now2 = (uint64_t)std::chrono::high_resolution_clock::now().time_since_epoch().count(); std::seed_seq seeds{now1, now2, thread_id, entropy}; std::mt19937 random_generator(seeds);
(seed_seq принимает initializer_list, по этому аргументы должны быть однотипными).
Зная что у Вихря Мерсена такое больше состояние, может возникнуть желание полностью заполнить его случайными числами, например вызвав random_device() 624 раза. Но это не имеет никакого практического смысла. Цель - это получить уникальную последовательность случайных чисел, и на практике для этого достаточно просто использовать текущее время.
Надо понимать, что ни один из стандартных ГПСЧ не является криптографически стойким, даже выдачу Вихря Мерсена можно предсказать получив всего 624 числа. Поэтому использование большой инициализирующей последовательности не дает никаких преимуществ в плане безопасности.
std::random_device
random_device - это генератор случайных чисел, реализация которого зависит от стандартной библиотеки. В зависимости от платформы и реализации стандартной библиотеки, это может быть:
криптографически стойкий системный генератор действительно случайных чисел, в т.ч.
инструкция процессора rdrand (libc++) чтение /dev/random или /dev/urandom (libstdc++) вызов RtlGenRandom() на Windows (vc++) обычный ГПСЧ который всегда выдает одни и те же числа (MinGW)
При этом если реализация использует /dev/(u)random и этот файл не удалось открыть, то будет брошено исключение.
Также чтение /dev/random может заблокировать работу программы до момента когда система накопит достаточно энтропии.
Поэтому std::random_device следует использовать только на тех системах и компиляторах про которые известно что она там работает как ГСЧ, и быть готовым к тому что эта функция очень медленная по сравнению с ГПСЧ.
(У random_device есть функция entropy(), но она бесполезна, т.к. на многих платформах она всегда возвращает 0 даже если используется ГСЧ а не ГПСЧ.)
Распределения
Классы распределений используют выдачу генераторов случайных чисел чтобы преобразовать ее в последовательность имеющую нужное распределение.
Некоторые классы распределений, например нормальное распределение и производные от него, имеют внутреннее состояние, поэтому не надо создавать новый объект распределения ка каждое случайное число.
std::mt19937 generator; std::normal_distribution distribution(0, 1); std::vector data; for (auto i = 0; i != 100; ++i) { data.push_back(distribution(generator)); // OK } for (auto i = 0; i != 100; ++i) { // ПЛОХО, не используется состояние распределения data.push_back(std::normal_distribution(3, 1)(generator)); }
Впрочем даже если и создавать новое распределение на каждое число, форма распределения меняется незначительно.
Примеры
Заменой кода с ::rand() из
::srand(::time(0)); for (int i = 0; i != n; i++) std::cout << ::rand() << '\0';
будет либо использование mt19937
std::mt19937 rand(::time(0)); // Лучше использовать high_resolution_clock for (int i = 0; i != n; i++) std::cout << rand() << '\0';
либо использование random_device (это нормально для программ уровня "Hello World")
std::random_device rand; for (int i = 0; i != n; i++) std::cout << rand() << '\0';
Более сложный пример с функтором-генератором случайных чисел:
#include #include #include #include #include #include
struct GaussGenerator { GaussGenerator(double mean, double stddev, std::uint32_t seed) : engine_(seed), distribution_(mean, stddev) {}
GaussGenerator(double mean, double stddev) : distribution_(mean, stddev) { using namespace std; seed_seq seeds{ (uint64_t)chrono::high_resolution_clock::now().time_since_epoch().count(), (uint64_t)chrono::system_clock::now().time_since_epoch().count(), (uint64_t)hash{}(this_thread::get_id()), }; engine_.seed(seeds); }
double operator()() { return distribution_(engine_); }
std::mt19937 engine_; std::normal_distribution distribution_; };
int main() { GaussGenerator rand(0, 1); for (int i = 0; i != 5; ++i) std::cout << rand() << '
'; }