Грунтовка мерсенновского твистера 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.
....
Мои вопросы:
-
Это миф или есть доля правды?
-
Если это что-то жизнеспособное, сколько битов следует игнорировать? как числа, которые я видел
кажется произвольным
Решение
Документ, указанный в первом комментарии, Mersenne Twister с улучшенной инициализацией, это не просто парень, он один из двух соавторов статьи, на которой основана реализация Boost.
Проблема с использованием одного 32-разрядного целого числа (4 байта) в качестве начального числа для этого генератора заключается в том, что внутреннее состояние генератора составляет 2496 байтов, в соответствии с Повысить документацию. Не слишком удивительно, что столь маленькое начальное число занимает некоторое время, чтобы распространиться на остальную часть внутреннего состояния генератора, в частности, поскольку Twister не предназначен для криптографической защиты.
Чтобы решить вашу проблему с необходимостью запустить генератор на некоторое время, чтобы начать, вам нужен альтернативный (и явный) конструктор.
template<typename SeedSeq> explicit mersenne_twister_engine(SeedSeq &);
Это дух третьего комментария, где вы инициализируете чем-то длиннее целого числа. Обеспечение последовательности происходит от некоторого генератора. Чтобы использовать энтропийный пул, запишите генератор в качестве адаптера из энтропийного пула, возвращая значения из пула по мере необходимости.
Другие решения
Других решений пока нет …