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

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

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

MT 19937 имеет следующие ожидаемые свойства:

  1. Он был разработан с целью иметь огромный период, размером 219937 − 1 (создатели алгоритма доказали это свойство). Этот период объясняет происхождение названия: это простое число Мерсенна, и некоторые из гарантий алгоритма зависят от внутреннего использования простых чисел Мерсенна. На практике, имеется мало причин использовать большие числа, чем это.
  2. Он имеет высокий порядок пространственного эквираспространения (см. также линейный конгруэнтный метод). Заметим, что это значит, по определению, что корреляция между последовательными значениями в выходной последовательности пренебрежимо мала.
  3. Он значительно быстрее, чем все остальные генераторы, за исключением статистически-дефектных генераторов.
  4. Он статистически случаен во всех выходных битах, и проходит строгие Тесты 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.

Ссылки

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home