Какой из <random>механизмов случайных чисел следует использовать на практике? станд :: mt19937?

Question

Предположим, вы хотите использовать средства C ++ <random> в практической программе (для некоторого определения "практический" - ограничения здесь являются частью этого вопроса). У вас есть код примерно такой:

int main(int argc, char **argv) {
    int seed = get_user_provided_seed_value(argc, argv);
    if (seed == 0) seed = std::random_device()();
    ENGINE g(seed);  // TODO: proper seeding?
    go_on_and_use(g);
}

Мой вопрос: какой тип вы должны использовать для ENGINE?

• Раньше я всегда говорил std::mt19937, потому что он быстро набирал текст и распознавал имя. Но в наши дни кажется, что все говорят , что Twister Mersenne Twister очень тяжелый и непригоден для кэширования и даже не проходит все статистические тесты, которые делают другие.

• Я хотел бы сказать std::default_random_engine, потому что это очевидный «дефолт». Но я не знаю, варьируется ли это от платформы к платформе, и Я не знаю, статистически ли это хорошо.

• Так как все на 64- битовая платформа в наши дни, должны ли мы хотя бы использовать std::mt19937_64 сверх std::mt19937?

• Я бы хотел сказать pcg64 или xoroshiro128, потому что они кажутся уважаемыми и легкий, но они вообще не существуют в <random>.

• Я ничего не знаю о minstd_rand, minstd_rand0, ranlux24, knuth_b и др. c. - конечно, они должны быть хороши для чего-то?

Очевидно, что здесь есть некоторые конкурирующие ограничения.

• Мощность двигателя. (<random> не имеет криптографически сильных PRNG, но все же некоторые из стандартизированных «слабее» других, верно?)

• sizeof двигатель.

• Скорость его operator().

• Удобство посева. mt19937 общеизвестно, что его трудно заполнить должным образом, потому что у него столько состояний для инициализации.

• Переносимость между поставщиками библиотек. Если foo_engine одного поставщика производит числа, отличные от foo_engine другого поставщика, это не подходит для некоторых приложений. (Надеюсь, это ничего не исключает, за исключением, может быть, default_random_engine.)

Взвешивая все эти ограничения как можно лучше, что бы вы назвали окончательной "наилучшей практикой пребывания в -стандарт-библиотека "ответ? Должен ли я просто продолжать использовать std::mt19937, или как?

Answer 1

C ++ Reference перечисляет все случайные механизмы, в настоящее время предоставляемые C ++. Однако выбор двигателей оставляет желать лучшего (например, см. Мой список высококачественных случайных генераторов ). Например:

• default_random_engine определяется реализацией, поэтому неизвестно, имеет ли движок статистический fl aws, о котором может заботиться приложение.
• linear_congruential_engine реализует линейный конгруэнтные генераторы. Однако они имеют тенденцию иметь низкое качество, если модуль не является простым и очень большим (не менее 64 бит). Кроме того, они не могут допустить больше семян, чем их модуль.
• minstd_rand0 и minstd_rand допускают только около 2 ^ 31 семян. knuth_b оборачивает minstd_rand0 и выполняет его перемешивание Бэйса-Дарема.
• mt19937 и mt19937_64 могут допустить гораздо больше семян, если их лучше инициализировать (например, путем инициализации std::seed_seq с несколькими выходами random_device, а не только один), но они используют около 2500 байтов состояния.
• ranlux24 и ranlux48 используют около 577 бит состояния, но они медленные (они работают по сохраняя некоторые и отбрасывая другие псевдослучайные выходные данные.)

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

• discard_block_engine отбрасывает некоторые выходов данного случайного механизма.
• shuffle_order_engine реализует тасовку Бэйса-Дарема данного случайного механизма.

Например, возможно, скажем, иметь Бэйс-Дарем перетасовка mt19937, ranlux24 или пользовательский linear_congruential_engine с shuffle_order_engine. Возможно, завернутый двигатель более качественный, чем оригинальный. Тем не менее, трудно предсказать статистическое качество нового движка без тестирования его .

Таким образом, в ожидании таких тестов кажется, что mt19937 является наиболее практичным движком в стандарте C ++ на данный момент. , Однако мне известно, по крайней мере, одно предложение добавить еще один механизм случайных чисел в будущие версии C ++ (см. C ++ paper P2075 ).

Answer 2

Согласно C ++ Reference , default_random_engine:

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

Так что для легкого использования вам не нужно беспокоиться о что угодно, семя default_random_engine с Epoch Time (time(0)), и этого было бы достаточно;)