Mersenne Twister считается хорошим. Черт, источник CPython говорит, что он «является одним из наиболее тщательно протестированных генераторов из существующих». Но что это значит? Когда меня просят перечислить свойства этого генератора, большинство из того, что я могу предложить, плохо:
- Он массивный и негибкий (например, без поиска или нескольких потоков),
- Он не проходит стандартные статистические тесты, несмотря на его огромный размер состояния,
- У него есть серьезные проблемы около 0, предполагая, что он рандомизирует себя довольно плохо,
- Это вряд ли быстро
и так далее. По сравнению с простыми ГСЧ, такими как XorShift *, это также безнадежно сложно.
Поэтому я искал некоторую информацию о том, почему это когда-либо считалось хорошим. Оригинальная статья содержит множество комментариев о «суперастрономическом» периоде и 623-мерном равнораспределении, говоря
Среди многих известных мер тесты, основанные на более высокой размерной однородности, такие как спектральный тест (см. Knuth [1981]) и тест k-распределения, описанные ниже, считаются наиболее сильными.
Но для этого свойства генератор разбит счетчиком достаточной длины! Это не комментирует локальные дистрибутивы, а это то, что вам действительно нужно в генераторе (хотя «локальный» может означать разные вещи). И даже CSPRNG не заботятся о таких больших периодах, поскольку это просто не важно.
В газете много математики, но, насколько я могу судить, из этого мало что касается качества случайности. Практически каждое упоминание об этом быстро возвращается к этим оригинальным, в основном бесполезным заявлениям.
Кажется, что люди запрыгнули на этот подножку за счет более старых, более надежных технологий. Например, если вы просто увеличиваете количество слов в LCG до 3 (намного меньше, чем «только 624» в Mersenne Twister) и выводите верхнее слово при каждом проходе, он проходит BigCrush ( более сложная часть набора тестов TestU01). ), несмотря на то, что Твистер не справился с этим ( бумага PCG, рис. 2 ). Учитывая это, а слабые доказательства того, мне удалось найти в поддержку Вихрь Мерсенна, то , что было причиной внимания в пользу его на другие варианты?
Это не чисто историческое. Мне попутно сказали, что Mersenne Twister, по крайней мере, более проверен на практике, чем, скажем, PCG random . Но так ли различают сценарии использования, что они могут работать лучше, чем наши тесты? Некоторые из Google предполагают, что это не так.
Короче говоря, мне интересно, как Mersenne Twister получил широкую положительную репутацию, как в историческом контексте, так и в других отношениях. С одной стороны, я, очевидно, скептически отношусь к его качествам, но с другой стороны трудно представить, что это произошло совершенно случайно.
Ответы:
MT считался хорошим в течение нескольких лет, пока не оказалось, что он оказался довольно плохим с более продвинутыми тестами TestU01 BigCrush и лучшими PRNG.
Например, таблица на pcg-random.org дает хороший обзор возможностей некоторых из наиболее часто используемых PRNG, где единственной «хорошей» особенностью Twister Mersenne является огромный период и возможность использовать seed (Воспроизводимые результаты), он проходит простые и быстрые тесты TestU01 SmallCrush, но не проходит некоторые из более новых статистических тестов качества, особенно TestU01 LinearComp Test и аккумуляторы TestU01 Crush и BigCrush.2219937
На этой странице перечислены функции Mersenne-Twister:
Положительные качества
Нейтральные качества
Отрицательные качества
Краткое описание : Mersenne Twister уже недостаточно хорош, но большинство приложений и библиотек еще не создано.
источник
Я - редактор, который принял статью MT в ACM TOMS еще в 1998 году, и я также являюсь разработчиком TestU01. Я не использую MT, но в основном MRG32k3a, MRG31k3p и LRSR113. Чтобы узнать больше об этом, о MT и о том, что еще есть, вы можете посмотреть следующие статьи:
F. Panneton, P. L'Ecuyer и M. Matsumoto, `` Улучшенные генераторы длинных периодов, основанные на линейных рекуррентах по модулю 2 '', Транзакции ACM по математическому программному обеспечению, 32, 1 (2006), 1-16.
P. L'Ecuyer, "Генерация случайных чисел", глава 3 Справочника по вычислительной статистике, JE Gentle, W. Haerdle и Y. Mori, eds., Second Edition, Springer-Verlag, 2012, 35-71. , https://link.springer.com/chapter/10.1007/978-3-642-21551-3_3
П. Экьюер, Д. Мангер, Б. Орешкин, Р. Симард, «Случайные числа для параллельных компьютеров: требования и методы», «Математика и компьютеры в симуляции», 135, (2017), 3-17. http://www.sciencedirect.com/science/article/pii/S0378475416300829?via%3Dihub
P. L'Ecuyer, `` Генерация случайных чисел с несколькими потоками для последовательных и параллельных компьютеров '' »предложил расширенное руководство« Труды зимней симуляционной конференции 2015 года », IEEE Press, 2015, 31-44.
источник
В этом отношении, как и алгоритмы сортировки, не существует PRNG "один размер для всех". Различные используются для разных целей, и существует большое разнообразие критериев проектирования и использования. Можно неправильно использовать PRNG, например, использовать один для криптографии, для которого он не предназначен. В статье Википедии о Мерсенне Твистере также упоминается, что она не была разработана для "моделирования Монте-Карло, которое требует независимых генераторов случайных чисел".
Как отмечено в Википедии, этот PRNG действительно используется в большом количестве языков программирования и приложений, даже в качестве PRNG по умолчанию. Потребовался бы почти социологический анализ, чтобы объяснить, почему один PRNG является предпочтительным. Некоторые возможные факторы, которые могут способствовать этому PRNG:
Автор имеет хорошие / сильные научные знания в области и работает в PRNGs в течение десятилетий.
Он был специально разработан, чтобы превзойти другие методы в то время.
Автор занимается внедрением и отслеживанием их, также способствуя им. Некоторые PRNG более теоретичны, и авторы не всегда заботятся о реальных реализациях.
Система хорошо поддерживается / обновляется на веб-странице.
Новые версии PRNG были разработаны для устранения недостатков. Не существует единственного алгоритма Мерсенна Твистера, он больше похож на разные версии и семейство вариантов, которые могут удовлетворить различные потребности.
Он был тщательно проанализирован / протестирован стандартным программным обеспечением для анализа случайности и передан независимыми органами.
Существует известный эффект, измеряемый для веб-сайтов и многих других контекстов, таких как научные цитаты, называемые «преференциальной привязанностью», которые можно измерить. Это в основном, где давно установленные исторические источники получают дальнейшее использование. Такой эффект может объяснить выбор PRNG с течением времени.
Другими словами, вы спрашиваете о феномене «популярности», который связан и связан с человеческим выбором и не строго привязан к конкретным качествам, но является своего рода сложным / возникающим свойством и взаимодействием между различными алгоритмами, пользователями и средой. / контексты использования.
Вот один такой независимый анализ алгоритма Мерсенна Твистера - Генератора псевдослучайных чисел и его вариантов по Jagannatam (15p). Заключительный абзац по сути является ответом на ваш вопрос. цитируя только 1- е несколько предложений:
источник