Грунтовка мерсенновского твистера PRNG

Question

Грунтовка мерсенновского твистера PRNG

Кажется, есть некоторая мифология вокруг использования mt19937, в частности, что когда-то посеянное «некоторое» количество битов, генерируемых генератором, должно быть проигнорировано, чтобы иметь как можно ближе к псевдослучайности, насколько это возможно.

Вот примеры кода, которые я видел:

boost::mt19937::result_type seed = 1234567; //taken from some entropy pool etc
boost::mt19937 prng(seed);
boost::uniform_int<unsigned int> dist(0,1000);
boost::variate_generator<boost::mt19937&,boost::uniform_int<unsigned int> > generator(prng,dist);

unsigned int skip = 10000;
while (skip--)
{
generator();
}

//now begin using for real.
....

Мои вопросы:

Это миф или есть доля правды?
Если это что-то жизнеспособное, сколько битов следует игнорировать? как числа, которые я видел
кажется произвольным

8

boost-random c++math random

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Документ, указанный в первом комментарии, Mersenne Twister с улучшенной инициализацией, это не просто парень, он один из двух соавторов статьи, на которой основана реализация Boost.

Проблема с использованием одного 32-разрядного целого числа (4 байта) в качестве начального числа для этого генератора заключается в том, что внутреннее состояние генератора составляет 2496 байтов, в соответствии с Повысить документацию. Не слишком удивительно, что столь маленькое начальное число занимает некоторое время, чтобы распространиться на остальную часть внутреннего состояния генератора, в частности, поскольку Twister не предназначен для криптографической защиты.

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

template<typename SeedSeq> explicit mersenne_twister_engine(SeedSeq &);

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

4