Mersenne Twister считается вредным

Mersenne Twister – очень распространенный генератор случайных чисел. Он используется в C, Python, Mathematica, Excel, PHP, Ruby … Новая статья предполагает, что этого не должно быть.

Случайное число

Больше мультяшных забав на xkcd, веб-комиксе о романтике, сарказме, математике и языках.

Качество используемых нами псевдослучайных чисел очень важно, и внедрение генератора Мерсенна Твистера, который является частным случаем линейного генератора F2, было частично ответом на открытие, что текущие генераторы были дефектными. В новом исследовании Себастьяно Винья, изобретателя xorshift + и xoroshiro128 +, используемых в движках JavaScript в Chrome, FIrefox и Safari, говорится:

«После того, как разработчики языка решили использовать Mersenne Twister, выбор был обречен на очень долгое время. Кроме того, проблемы Mersenne Twister не сразу обнаруживаются в повседневных приложениях, и большинство пользователей действительно заинтересованы в качестве их ГПСЧ сделает осознанный выбор, вместо того, чтобы полагаться на стандартный ГПСЧ той среды программирования, которую они используют. Таким образом, не было сильной мотивации двигаться в сторону более совершенного ГПСЧ ».

Частично аргумент в пользу отказа от Mersenne Twister заключается в том, что тесты, которые он провалил, не были важны для реального использования генератора. В частности, если вы возьмете биты, сгенерированные как равномерно распределенные в интервале от 0 до 1, а затем примените нелинейное преобразование к другому распределению, то дефекты исчезнут. Это действительно способ, которым во многих симуляциях используются псевдослучайные числа, но в новой статье приводятся примеры, когда это не так.

Итог всех этих примеров:

“F2-линейные генераторы не проходят статистические тесты, которые могут повлиять на реальные приложения. Их следует использовать с осторожностью и только в контексте, когда есть уверенность, что к их выходным данным будут применены сильно нелинейные операции, поэтому их дефекты будут устранены или полностью скрыты. В частности, линейные генераторы никогда не должны использоваться в качестве генераторов общего назначения, если их выход не скремблируется соответствующим образом путем объединения его с другими, нелинейными генераторами или путем применения нелинейных карт. Текущее опасное повсеместное распространение Mersenne Twister в качестве основного ГПСЧ во многих средах – это исторический артефакт, о котором мы, как сообщество, должны позаботиться. Более того, некоторые рекламируемые преимущества Mersenne Twister, такие как повторная параметризация, на самом деле не работают должным образом при внимательном рассмотрении ”

Также, похоже, есть простое решение проблемы – использование скремблера, как в собственном xoshiro256 ++ автора, означает, что у нас есть генератор, который не проходит ни один известный статистический тест. Дело в том, что есть более эффективные способы выполнения работы, и мы их не используем.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *