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

#cpp #cpp11

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

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

Ответы

Ответ 1

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

В стандартной библиотеке есть три генератора псевдослучайных чисел (ГПСЧ, англ. 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() << '\n';
}


Ответ 2

Видимо, многим людям не дает покоя все нарастающая сложность софта и они (в меру
своих сил) пытаются с ней совладать.

Недолгий поиск по сети реализаций ГПСЧ принес свои плоды -- PCG, A Family of Better
Random Number Generators.

О своих недостатках они  пишут, что 


  
  New
  Although it is less trivial to predict than many mainstream generators, that does
not mean it should be considered
  crypographically secure. Exactly how hard it is to break different
  members of the PCG family is unknown at this time.
  


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

А вот и образец кода одного из генераторов:

// *Really* minimal PCG32 code / (c) 2014 M.E. O'Neill / pcg-random.org
// Licensed under Apache License 2.0 (NO WARRANTY, etc. see website)

typedef struct { uint64_t state;  uint64_t inc; } pcg32_random_t;

uint32_t pcg32_random_r(pcg32_random_t* rng)
{
    uint64_t oldstate = rng->state;
    // Advance internal state
    rng->state = oldstate * 6364136223846793005ULL + (rng->inc|1);
    // Calculate output function (XSH RR), uses old state for max ILP
    uint32_t xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u;
    uint32_t rot = oldstate >> 59u;
    return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
}