Виток Мерсенна
Материал из Википедии — свободной энциклопедии
Виток Мерсенна (Mersenne twister) — это генератор псевдослучайных чисел, разработанный в 1997 японскими учёными Макото Мацумото (松本 眞) и Такуджи Нишимура (西村 拓士). Он обеспечивает быструю генерацию высококачественных псевдослучайных чисел, так как изначально был разработан с учётом ошибок, найденных в других алгоритмах.
Существуют по меньшей мере два общих варианта алгоритма, различающихся только размером использующегося простого числа Мерсенна. Новейший и наиболее распространённый называется Mersenne Twister MT 19937.
MT 19937 имеет следующие ожидаемые свойства:
- Он был разработан с целью иметь огромный период, размером 219937 − 1 (создатели алгоритма доказали это свойство). Этот период объясняет происхождение названия: это простое число Мерсенна, и некоторые из гарантий алгоритма зависят от внутреннего использования простых чисел Мерсенна. На практике, имеется мало причин использовать большие числа, чем это.
- Он имеет высокий порядок пространственного эквираспространения (см. также линейный конгруэнтный метод). Заметим, что это значит, по определению, что корреляция между последовательными значениями в выходной последовательности пренебрежимо мала.
- Он значительно быстрее, чем все остальные генераторы, за исключением статистически-дефектных генераторов.
- Он статистически случаен во всех выходных битах, и проходит строгие Тесты DIEHARD.
[править] Как работает алгоритм
Алгоритм является витковым регистром сдвига с обобщённой отдачей (twisted generalised feedback shift register, TGFSR). "Виток" — это преобразование, которое обеспечивает эквираспределение генерируемых чисел в 623 измерениях (линейные конгруэнтные генераторы могут в лучшем случае гарантировать разумное распределение в 5 измерениях).
В отличие от Блюм-Блюм-Шуба, алгоритм в его исконной форме не подходит для криптографии. Для многих других приложений, он быстро становится избранным генератором случайных чисел.
[править] Литература
- M. Matsumoto and T. Nishimura, Mersenne twister: A 623-dimensionally equidistributed uniform pseudorandom number generator, ACM Trans. on Modeling and Computer Simulations, 1998.
[править] Ссылки
- Mersenne Twister home page, with C code
- The GNU Scientific Library (GSL), containing an implementation of the Mersenne Twister
- A claimed implementation of the Mersenne Twister algorithm
- Implementation of Mersenne Twister for REALbasic (requires REALbasic 2006r1 or greater)
- Implementation of Mersenne Twister for Lisp
- Implementation of Mersenne Twister for C#
- Implementation of Mersenne Twister for Ada
- Implementation of Mersenne Twister as an add-in for Microsoft Excel
- CPAN module implementing the Mersenne Twister for use with Perl
- It also is, apparently, implemented in gLib and the standard libraries of at least PHP, Python and Ruby.
