Виток Мерсенна

Вихрь Мерсенна (Mersenne twister) — это генератор псевдослучайных чисел (ГПСЧ), разработанный в 1997 японскими учёными Макото Мацумото (松本 眞) и Такудзи Нисимура (西村 拓士). Их работа основывается на свойствах простых чисел Мерсенна (отсюда название) и обеспечивает быструю генерацию высококачественных псевдослучайных чисел. Вихрь Мерсенна лишен многих недостатков присущих другим ГПСЧ таких как малый период, предсказуемость, легко выявляемая статистическая зависимость. Тем не менее этот генератор не является криптостойким, что ограничивает его использование в криптографии.

Существуют по меньшей мере два общих варианта алгоритма, различающихся только размером использующегося простого числа Мерсенна, наиболее распространённым из которых является MT19937.

Свойства

Вихрь Мерсенна является витковым регистром сдвига с обобщённой отдачей (twisted generalised feedback shift register, TGFSR). «Вихрь» — это преобразование, которое обеспечивает равномерное распределение генерируемых псевдослучайных чисел в 623 измерениях (для линейных конгруэнтных генераторов оно ограничено 5-ю измерениями). Поэтому корреляция между последовательными значениями в выходной последовательности Вихря Мерсенна пренебрежимо мала.

Вихрь Мерсенна имеет огромный период, а именно, доказано, что его период равен числу Мерсенна 2¹⁹⁹³⁷ − 1, что более чем достаточно для многих практических приложений.

Существуют эффективные реализации Вихря Мерсенна, превосходящие по скорости многие стандартные ГПСЧ (в частности, в 2-3 раза быстрее линейных конгруэнтных генераторов). Вихрь Мерсенна реализован в библиотеке PHP, Руби.

Выдаваемые Вихрем Мерсенна псевдослучайные числа успешно проходят тесты DIEHARD, что говорит об их хороших статистических свойствах.

Литература

• 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(англ.)
• Cuba — a library for multidimensional numerical integration
• 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(англ.) возвращает 404 (Проверено 4 марта 2009)
• Implementation of Mersenne Twister for C#(англ.) возвращает 404 (Проверено 4 марта 2009)
• 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(англ.)