Почему Mersenne Twister считается хорошим?

39

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 получил широкую положительную репутацию, как в историческом контексте, так и в других отношениях. С одной стороны, я, очевидно, скептически отношусь к его качествам, но с другой стороны трудно представить, что это произошло совершенно случайно.

Veedrac
источник
2
Я думаю ты прав. Мерсенн Твистер ничего особенного. Это просто хорошо известно (и многие другие известные PRNG оказываются хуже). Есть и другие PRNG, которые тоже довольно хороши. Для еще лучшего PRNG можно использовать криптографический PRNG. Я не уверен, какой ответ можно дать, кроме того, что «в твоих рассуждениях нет ничего плохого».
DW
1
Я думаю, что вопрос, который вы должны задать, заключается не в том, хорош ли MT (поскольку он, по многим показателям), а в том, почему он используется чаще, чем альтернативы, такие как PCG или XorShift. Ответ, вероятно, заключается в том, что он существовал дольше и был лучшим разумным значением по умолчанию в течение длительного времени (в годы Интернета).
псевдоним
1
@vzn «еще одно соображение - это время генерации;« качество »PRNG достигается за счет времени работы» → За исключением того, что Mersenne Twister медленнее и хуже, чем резонансно большой LCG. См. Рис. 16 в документе PCG. (О том, прочитал ли я газету: я прочитал большинство нематематических частей статьи Мерсенна Твистера и всю случайную бумагу PCG. Я, в основном, снял третье.)
Veedrac
1
Вы говорите об XorShift или алгоритмах KISS?
gnasher729
1
@ gnasher729 Я упоминаю XorShift *, но на самом деле я не совсем конкретен в отношении конкретной альтернативы. Я не знал о KISS, FWIW.
Veedrac

Ответы:

15

MT считался хорошим в течение нескольких лет, пока не оказалось, что он оказался довольно плохим с более продвинутыми тестами TestU01 BigCrush и лучшими PRNG.

Например, таблица на pcg-random.org дает хороший обзор возможностей некоторых из наиболее часто используемых PRNG, где единственной «хорошей» особенностью Twister Mersenne является огромный период и возможность использовать seed (Воспроизводимые результаты), он проходит простые и быстрые тесты TestU01 SmallCrush, но не проходит некоторые из более новых статистических тестов качества, особенно TestU01 LinearComp Test и аккумуляторы TestU01 Crush и BigCrush.2219937

На этой странице перечислены функции Mersenne-Twister:

Положительные качества

  • Создает 32-битные или 64-битные числа (таким образом, используемые в качестве источника случайных битов)
  • Проходит большинство статистических тестов

Нейтральные качества

  • Неоправданно большой период2219937-1
  • 623-мерно равнораспределенный
  • Период может быть разделен для эмуляции нескольких потоков

Отрицательные качества

  • Не проходит некоторые статистические тесты, всего с 45 000 номеров.
  • Предсказуемо - после 624 выходов мы можем полностью предсказать его выход.
  • Состояние генератора занимает 2504 байта ОЗУ - напротив, чрезвычайно полезный генератор с периодом, который больше, чем кто-либо может использовать, может уместиться в 8 байтов ОЗУ.
  • Не особенно быстро.
  • Не особенно экономно. Генератор использует 20000 бит для хранения своего внутреннего состояния (20032 бит на 64-битных машинах), но имеет период только , что в 263 (или 295) раза меньше, чем у идеального генератора такого же размера.2219937
  • Неравномерно по выходу; генератор может попасть в «плохие состояния», которые медленно восстанавливаются.
  • Семена, которые отличаются незначительно, занимают много времени, чтобы расходиться друг с другом; посев должен быть сделан осторожно, чтобы избежать плохих состояний.
  • Несмотря на то, что возможен скачок вперед, алгоритмы для этого медленны в вычислениях (т. Е. Требуют нескольких секунд) и редко обеспечиваются реализациями.

Краткое описание : Mersenne Twister уже недостаточно хорош, но большинство приложений и библиотек еще не создано.

rurban
источник
7
Спасибо за хорошее резюме! Тем не менее, я обеспокоен тем, что единственным очевидным источником для вашего поста является веб-сайт, который фактически является рекламой для другого семейства генераторов случайных чисел, которые еще не прошли рецензирование. Сам сайт не предлагает никаких ссылок на записи, но предлагаемая статья, кажется, содержит много. Следовательно, я думаю, что вы можете улучшить свой ответ для контекста здесь (критика МТ), дав ссылки на отдельные пункты.
Рафаэль
10
2219937295×22199372219945
1
«Предсказуемый» - MT не предназначен для криптографического PRNG, поэтому, пожалуйста, отредактируйте свой ответ.
Джейсон С
«Mersenne Twister уже недостаточно хорош»: что рекомендуется, если безопасность не имеет значения, важна посадка семян и скорость? (Мерсенн был достаточно быстр)
Мартин Тома
8

Я - редактор, который принял статью 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.

Пьер Л'Экуайер
источник
3
Спасибо за Ваш ответ! Не могли бы вы добавить что-нибудь к вопросу? 1) Почему вы думали, что MT был хорошим (или, по крайней мере, заслуживающим публикации) тогда? 2) Почему вы не думаете, что это достаточно хорошо для использования?
Рафаэль
Спасибо за добавление этого ценного исторического контекста. Мне также любопытны вопросы Рафаэля и ваши личные мысли, когда вы приняли газету.
Veedrac
5

В этом отношении, как и алгоритмы сортировки, не существует PRNG "один размер для всех". Различные используются для разных целей, и существует большое разнообразие критериев проектирования и использования. Можно неправильно использовать PRNG, например, использовать один для криптографии, для которого он не предназначен. В статье Википедии о Мерсенне Твистере также упоминается, что она не была разработана для "моделирования Монте-Карло, которое требует независимых генераторов случайных чисел".

Как отмечено в Википедии, этот PRNG действительно используется в большом количестве языков программирования и приложений, даже в качестве PRNG по умолчанию. Потребовался бы почти социологический анализ, чтобы объяснить, почему один PRNG является предпочтительным. Некоторые возможные факторы, которые могут способствовать этому PRNG:

  • Автор имеет хорошие / сильные научные знания в области и работает в PRNGs в течение десятилетий.

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

  • Автор занимается внедрением и отслеживанием их, также способствуя им. Некоторые PRNG более теоретичны, и авторы не всегда заботятся о реальных реализациях.

  • Система хорошо поддерживается / обновляется на веб-странице.

  • Новые версии PRNG были разработаны для устранения недостатков. Не существует единственного алгоритма Мерсенна Твистера, он больше похож на разные версии и семейство вариантов, которые могут удовлетворить различные потребности.

  • Он был тщательно проанализирован / протестирован стандартным программным обеспечением для анализа случайности и передан независимыми органами.

  • Существует известный эффект, измеряемый для веб-сайтов и многих других контекстов, таких как научные цитаты, называемые «преференциальной привязанностью», которые можно измерить. Это в основном, где давно установленные исторические источники получают дальнейшее использование. Такой эффект может объяснить выбор PRNG с течением времени.

Другими словами, вы спрашиваете о феномене «популярности», который связан и связан с человеческим выбором и не строго привязан к конкретным качествам, но является своего рода сложным / возникающим свойством и взаимодействием между различными алгоритмами, пользователями и средой. / контексты использования.

Вот один такой независимый анализ алгоритма Мерсенна Твистера - Генератора псевдослучайных чисел и его вариантов по Jagannatam (15p). Заключительный абзац по сути является ответом на ваш вопрос. цитируя только 1- е несколько предложений:

Мерсенн Твистер теоретически доказал, что он хороший PRNG, с длительным периодом и высокой равномерностью распределения. Он широко используется в областях моделирования и модуляции. Дефекты, обнаруженные пользователями, были исправлены изобретателями. MT был обновлен, чтобы использовать и быть совместимым с новыми технологиями CPU, такими как SIMD и параллельные конвейеры, в своей версии SFMT.

ВЗН
источник
2
Спасибо. Однако то, что вы говорите, звучит довольно расплывчато, например: «Оно было специально разработано, чтобы превосходить другие методы в то время». и «Он был тщательно проанализирован / протестирован стандартным программным обеспечением для анализа случайности и передан независимыми властями», что является именно теми утверждениями, к которым я с подозрением отношусь. Я немного погрузлюсь в газету, чтобы посмотреть, прояснит ли это ситуацию.
Veedrac
Еще одна вещь, которую необходимо учитывать, - это научная воспроизводимость. Многие ученые, работающие в области моделирования Монте-Карло, прилагают много усилий, чтобы убедиться, что программа в целом выдает одинаковый результат при одинаковом начальном значении, независимо от количества потоков. Многие из них требуют совместимости «ошибка за ошибкой» с эталонной реализацией PRNG.
псевдоним
2
Вы также говорите: «Новые версии PRNG были разработаны для борьбы со слабостями», но, учитывая, что большинство реализаций являются первой версией стандартного болота, для меня это больше похоже на критику. Я также немного удивлен, увидев, что «система хорошо поддерживается / обновляется на веб-странице». - сколько поддержки действительно нужно LCG !?
Veedrac
@ Псевдоним я не очень следую. Почему это исключает использование другого генератора? Очевидно, вы должны использовать тот же генератор при повторном запуске тестов, но почему для новых тестов?
Veedrac
в оригинальном и последующих статьях нет особой расплывчатости во всем научном анализе, и первоначальный вопрос несколько «загружен» таким образом (на самом деле используется много ГНПО с меньшим количеством анализа / поддержки). Что касается псевдонимов, то на самом деле все PRNG повторяются с использованием одних и тех же начальных начальных чисел, только аппаратные генераторы - нет (и на самом деле они больше не являются PRNG, а «реальным физическим шумом / случайностью»). не уверен, как это трудно обеспечить с несколькими потоками (не знаю, почему отдельные потоки не могут использовать одинаковый алгоритм с разными
начальными значениями