Мерсенн Твистер

Вихрь Мерсенна является псевдослучайных чисел (ПСЧ). Это, безусловно, наиболее широко используемый ГПСЧ общего назначения. ^[1] Его название происходит от того факта, что длина периода выбрана как простое число Мерсенна .

Mersenne Twister был разработан в 1997 году Макото Мацумото  [ джа ] (松本 眞) и Такудзи Нисимура (西村 拓 士) . ^[2] Он был разработан специально для исправления большинства недостатков, обнаруженных в старых ГПСЧ.

Наиболее часто используемая версия алгоритма Мерсенна Твистера основана на простом числе Мерсенна 2 ¹⁹⁹³⁷ -1. Стандартная реализация этого, MT19937, использует 32-битную длину слова. Существует еще одна реализация (с пятью вариантами ^[3] ), в которой используется длина слова 64 бита, MT19937-64; он генерирует другую последовательность.

Внедрение в программных системах [ править ]

Mersenne Twister - это ГПСЧ по умолчанию для следующих программных систем: Dyalog APL , ^[4] Microsoft Excel , ^[5] GAUSS , ^[6] GLib , ^[7] GNU Multiple Precision Arithmetic Library , ^[8] GNU Octave , ^[9] Научная библиотека GNU , ^[10] gretl , ^[11] IDL , ^[12] Джулия , ^[13] CMU Common Lisp , ^[14] Embeddable Common Lisp , ^[15] Steel Bank Common Lisp , ^[16] Maple, ^[17] MATLAB , ^[18] Free Pascal , ^[19] PHP , ^[20] Python , ^{[21] [22] [23]} R , ^[24] Ruby , ^[25] SageMath , ^[26] Scilab , ^{[27] ]} Stata . ^[28]

Он также доступен в Apache Commons , ^[29] в стандартном C ++ (так как C ++ 11 ), ^{[30] [31]} и в Mathematica . ^[32] Надстройка на реализацию обеспечивается во многих программных библиотеках, в том числе Boost , C ++ библиотек , ^[33] CUDA библиотека , ^[34] и численная библиотеки NAG . ^[35]

Mersenne Twister - один из двух PRNG в SPSS : второй генератор сохранен только для совместимости со старыми программами, а Mersenne Twister считается «более надежным». ^[36] Mersenne Twister также является одним из ГПСЧ в SAS : другие генераторы устарели и устарели. ^[37] Mersenne Twister - это ГПСЧ по умолчанию в Stata , другой - KISS , для совместимости со старыми версиями Stata. ^[38]

Преимущества [ править ]

• Имеет разрешительную лицензию и не содержит патентов для всех вариантов, кроме CryptMT.
• Проходит множество тестов на статистическую случайность, включая тесты Дихарда и большинство, но не все тесты TestU01 . ^[39]
• Очень длинный период 2 ¹⁹⁹³⁷  - 1. Обратите внимание, что, хотя длительный период не является гарантией качества в генераторе случайных чисел, короткие периоды, такие как 2 ^32, обычно используемые во многих старых программных пакетах, могут быть проблематичными. ^[40]
• k -распределенный с 32-битной точностью для каждого 1 ≤ k ≤ 623 (определение k -распределенного, см. ниже )
• Реализации обычно создают случайные числа быстрее, чем истинные случайные методы. Исследование показало, что Mersenne Twister создает 64-битные случайные числа с плавающей запятой примерно в двадцать раз быстрее, чем аппаратно реализованный набор команд RDRAND на базе процессора . ^[41]

Недостатки [ править ]

• Относительно большой буфер состояния, 2,5 КБ , если не используется вариант TinyMT (обсуждается ниже).
• Посредственная пропускная способность по современным стандартам, если не используется вариант SFMT (обсуждается ниже). ^[42]
• Демонстрирует два явных отказа (линейная сложность) как в Crush, так и в BigCrush в наборе TestU01. Тест, как и Мерсенн Твистер, основан на алгебре F ₂ . ^[39] Есть ряд других генераторов, которые проходят все тесты (и множество генераторов, которые терпят неудачу) ^{[ требуется пояснение ]} .
• Несколько экземпляров, которые отличаются только начальным значением (но не другими параметрами), обычно не подходят для моделирования методом Монте-Карло , требующего независимых генераторов случайных чисел, хотя существует метод выбора нескольких наборов значений параметров. ^{[43] [44]}
• Плохая диффузия: может потребоваться много времени, чтобы начать генерировать выходные данные, которые проходят тесты на случайность , если начальное состояние сильно неслучайно, особенно если начальное состояние имеет много нулей. Следствием этого является то, что два экземпляра генератора, запущенные с почти одинаковыми начальными состояниями, обычно выводят почти одинаковую последовательность для многих итераций, прежде чем в конечном итоге расходятся. Обновление алгоритма MT в 2002 году улучшило инициализацию, так что начало с такого состояния маловероятно. ^[45] Версия с графическим процессором (MTGP) считается даже лучше. ^[46]
• Содержит подпоследовательности, в которых нулей больше, чем единиц. Это усиливает плохую диффузионную способность и затрудняет восстановление из состояний с множеством нулей.
• Не является криптографически безопасным , если не используется вариант CryptMT (обсуждается ниже). Причина в том, что соблюдение достаточного количества итераций (624 в случае MT19937, поскольку это размер вектора состояния, из которого производятся будущие итерации) позволяет прогнозировать все будущие итерации.

Альтернативы [ править ]

Альтернативный генератор, WELL ("Well Equidistributed Long-period Linear"), предлагает более быстрое восстановление, равную случайность и почти равную скорость. ^[47]

Генераторы xorshift и их варианты Marsaglia являются самыми быстрыми в классе LFSR. ^[48]

64-битные MELG («64-битные максимально равнораспределенные F ₂ -линейные генераторы с простым периодом Мерсенна») полностью оптимизированы с точки зрения свойств k-распределения. ^[49]

Семейство ACORN (опубликовано в 1989 г.) - это еще один k-распределенный ГПСЧ, который показывает скорость вычислений, аналогичную MT, и лучшие статистические свойства, поскольку он удовлетворяет всем текущим (2019) критериям TestU01; при использовании с соответствующим выбором параметров ACORN может иметь произвольно длительный период и точность.

Семейство PCG - это более современный долгопериодический генератор с лучшей локализацией кэша и менее обнаруживаемым смещением при использовании современных методов анализа. ^[50]

k -распределение [ править ]

Последовательность псевдослучайных х _I из W - битовых целых чисел периода Р называется к-распределенной для v точности битовое , если выполнено следующее.

Пусть trunc _v (x) обозначает число, образованное старшими v битами x , и рассмотрим P из k v -битных векторов

${\ displaystyle ({\ text {trunc}} _ {v} (x_ {i}), \, {\ text {trunc}} _ {v} (x_ {i + 1}), \, ..., \, {\ text {trunc}} _ {v} (x_ {i + k-1})) \ quad (0 \ leq i <P)}$.

Тогда каждая из 2 ^kv возможных комбинаций битов встречается одинаковое количество раз за период, за исключением комбинации всех нулей, которая встречается один раз реже.

Алгоритмическая деталь [ править ]

Для w- битного слова Twister Мерсенна генерирует целые числа в диапазоне [0, 2 ^w −1].

Алгоритм Мерсенна Твистера основан на матричной линейной рекуррентности над конечным двоичным полем F ₂ . Алгоритм представляет собой сдвиговый регистр со скрученной обобщенной обратной связью ^[51] (скрученный GFSR или TGFSR) рациональной нормальной формы (TGFSR (R)) с отражением и регулировкой состояния битов. Основная идея состоит в том, чтобы определить ряд с помощью простого рекуррентного отношения, а затем вывести числа в форме , где - обратимая матрица F _2, называемая матрицей темперирования .${\ displaystyle x_ {i}}$${\ displaystyle x_ {i} T}$${\ displaystyle T}$

Общий алгоритм характеризуется следующими величинами (некоторые из этих объяснений имеют смысл только после прочтения остальной части алгоритма):

• w : размер слова (в битах)
• n : степень рецидива
• m : среднее слово, смещение, используемое в рекуррентном отношении, определяющем серию x , 1 ≤ m < n
• r : точка разделения одного слова или количество бит нижней битовой маски, 0 ≤ r ≤ w - 1
• a : коэффициенты матрицы скручивания рациональной нормальной формы
• b , c : битовые маски темперирования TGFSR (R)
• s , t : сдвиги долота отпуска TGFSR (R)
• u , d , l : дополнительные смены / маски для закалки Mersenne Twister

с ограничением, что 2 ^{nw  -  r}  - 1 - простое число Мерсенна. Этот выбор упрощает тест на примитивность и тест k- распределения , которые необходимы при поиске параметров.

Ряд x определяется как ряд w -битных величин с рекуррентным соотношением:

${\ displaystyle x_ {k + n}: = x_ {k + m} \ oplus \ left (({x_ {k}} ^ {u} \ mid \ mid {x_ {k + 1}} ^ {l}) A \ right) \ qquad \ qquad k = 0,1, \ ldots}$

где означает конкатенацию битовых векторов (с верхними битами слева), побитовое исключающее ИЛИ (XOR), означает верхние биты и означает нижние биты . Преобразование скручивания A определяется в рациональной нормальной форме как:${\ displaystyle \ mid \ mid}$${\ displaystyle \ oplus}$${\ displaystyle {x_ {k}} ^ {u}}$${\ displaystyle wr}$${\ displaystyle x_ {k}}$${\ displaystyle x_ {k + 1} ^ {l}}$${\displaystyle r}$${\displaystyle x_{k+1}}$

${\displaystyle A={\begin{pmatrix}0&I_{w-1}\\a_{w-1}&(a_{w-2},\ldots ,a_{0})\end{pmatrix}}}$

с I _{n  - 1} в качестве ( n  - 1) × ( n  - 1) единичной матрицы. Преимущество рациональной нормальной формы состоит в том, что умножение на A может быть эффективно выражено как: (помните, что здесь умножение матриц выполняется в F ₂ , и поэтому побитовое исключающее ИЛИ заменяет сложение)

${\displaystyle {\boldsymbol {x}}A={\begin{cases}{\boldsymbol {x}}\gg 1&x_{0}=0\\({\boldsymbol {x}}\gg 1)\oplus {\boldsymbol {a}}&x_{0}=1\end{cases}}}$

где x ₀ - младший бит x .

Как и TGFSR (R), Mersenne Twister каскадируется с преобразованием темперирования, чтобы компенсировать уменьшенную размерность равнораспределения (из-за выбора A в рациональной нормальной форме). Обратите внимание, что это эквивалентно использованию матрицы where для обратимой матрицы, и поэтому анализ характеристического полинома, упомянутый ниже, все еще сохраняется.${\displaystyle A}$${\displaystyle A=T^{-1}AT}$${\displaystyle T}$

Как и в случае с A , мы выбираем преобразование темперирования, чтобы оно было легко вычислимым, и поэтому на самом деле не конструируем само T. В случае Mersenne Twister закалка определяется как

y  : = x  ⊕ (( x  >>  u ) &  d )

y  : = y  ⊕ (( y  <<  s ) &  b )

y  : = y  ⊕ (( y  <<  t ) &  c )

z  : = y  ⊕ ( y  >>  l )

где x - следующее значение из серии, y - временное промежуточное значение, z - значение, возвращаемое алгоритмом, с <<, >> в качестве побитового сдвига влево и вправо, а & - в качестве побитового и . Первое и последнее преобразования добавляются для улучшения равнораспределения младших битов. Из свойства TGFSR требуется достижение верхней границы равнораспределения для верхних битов.${\displaystyle s+t\geq \lfloor w/2\rfloor -1}$

Коэффициенты для MT19937:

• ( ш , п , м , г ) = (32, 624, 397, 31)
• а  = 9908B0DF ₁₆
• ( u , d ) = (11; FFFFFFFF ₁₆ )
• ( s , b ) = (7, 9D2C5680 ₁₆ )
• ( t , c ) = (15, EFC60000 ₁₆ )
• l  = 18

Обратите внимание, что 32-битные реализации Mersenne Twister обычно имеют d  = FFFFFFFF ₁₆ . В результате d иногда опускается в описании алгоритма, поскольку побитовое и с d в этом случае не имеет никакого эффекта.

Коэффициенты для MT19937-64: ^[52]

• ( ш , п , м , г ) = (64, 312, 156, 31)
• а  = B5026F5AA96619E9 ₁₆
• ( u , d ) = (29, 5555555555555555 ₁₆ )
• ( s , b ) = (17, 71D67FFFEDA60000 ₁₆ )
• ( t , c ) = (37, FFF7EEE000000000 ₁₆ )
• l  = 43

Инициализация [ править ]

Состояние, необходимое для реализации Mersenne Twister, представляет собой массив из n значений по w бит каждое. Для инициализации массива используется w- битное начальное значение для предоставления от x ₀ до x _{n  - 1} путем установки x ₀ на начальное значение и последующей установки

x _i = f × ( x _{i −1} ⊕ ( x _{i −1} >> ( w −2))) + i

для i от 1 до n −1. Первое значение, которое затем генерирует алгоритм, основано на x _n , а не на x ₀ . Константа f формирует еще один параметр генератора, но не является частью самого алгоритма. Значение f для MT19937 составляет 1812433253, а для MT19937-64 - 6364136223846793005. ^[52]

Сравнение с классической GFSR [ править ]

Для того , чтобы достичь 2 ^{NW  -  г}  - 1 теоретический верхний предел периода Т ДГФС , φ _В ( т ) должен быть примитивный многочлен , φ _B ( т ) , являющийся характеристический полином из

${\displaystyle B={\begin{pmatrix}0&I_{w}&\cdots &0&0\\\vdots &&&&\\I_{w}&\vdots &\ddots &\vdots &\vdots \\\vdots &&&&\\0&0&\cdots &I_{w}&0\\0&0&\cdots &0&I_{w-r}\\S&0&\cdots &0&0\end{pmatrix}}{\begin{matrix}\\\\\leftarrow m{\hbox{-th row}}\\\\\\\\\end{matrix}}}$

${\displaystyle S={\begin{pmatrix}0&I_{r}\\I_{w-r}&0\end{pmatrix}}A}$

Преобразование скручивания улучшает классический GFSR со следующими ключевыми свойствами:

• Период достигает теоретического верхнего предела 2 ^{nw  -  r}  - 1 (кроме случая, когда он инициализирован с помощью 0)
• Равное распределение в n измерениях (например, линейные конгруэнтные генераторы могут в лучшем случае управлять разумным распределением в пяти измерениях)

Псевдокод [ править ]

Следующий псевдокод реализует общий алгоритм Мерсенна Твистера. Константы w , n , m , r , a , u , d , s , b , t , c , l и f такие же, как в описании алгоритма выше. Предполагается, что int представляет тип, достаточный для хранения значений с w битами:

 // Создаем массив длины n для хранения состояния генератора  int [0 .. n -1] MT int index: = n +1 const int lower_mask = (1 << r ) - 1 // То есть двоичный количество r 1  const int upper_mask = младшие w битов ( не lower_mask)  // Инициализируем генератор из начального значения  функции seed_mt ( int seed) { индекс: = n MT [0]: = seed for i от 1 до ( n - 1) { // перебираем каждый элемент MT [i]: = младшие w битов ( f * (MT [i-1] xor (MT [i-1] >> ( w - 2))) + i) } }  // Извлекаем умеренное значение на основе MT [index]  // вызываем twist () каждые n чисел  function extract_number () { if index> = n { if index> n { error «Генератор никогда не был засеян» // Альтернативно, seed с постоянное значение; 5489 используется в справочном коде C [53] } крутить() }  int y: = MT [индекс] y: = y xor ((y >> u ) и  d ) y: = y xor ((y << s ) и  b ) y: = y xor ((y << t ) и  c ) y: = y xor (y >> l )  index: = index + 1 вернуть младшие w битов (y) }  // Генерируем следующие n значений из серии x_i  function twist () { для i от 0 до ( n -1) { int x: = (MT [i] and upper_mask) + (MT [(i + 1) mod  n ] and lower_mask) int xA: = x >> 1 if (x mod 2)! = 0 { // младший бит x равен 1 xA: = xA xor  a } MT [i]: = MT [(i + m ) mod  n ] xor xA } индекс: = 0 }

Варианты [ править ]

CryptMT [ править ]

CryptMT - это потоковый шифр и криптографически безопасный генератор псевдослучайных чисел, который внутренне использует Mersenne Twister. ^{[54] [55]} Он был разработан Мацумото и Нисимура вместе с Марико Хагита и Муцуо Сайто. Он был отправлен в проект eSTREAM сети eCRYPT . ^[54] В отличие от Mersenne Twister или других его производных, CryptMT запатентован .

MTGP [ править ]

MTGP - это вариант Mersenne Twister, оптимизированный для графических процессоров, опубликованный Муцуо Сайто и Макото Мацумото. ^[56] Базовые операции линейной рекурсии расширены из MT, и параметры выбраны, чтобы позволить многим потокам вычислять рекурсию параллельно, совместно используя свое пространство состояний, чтобы уменьшить нагрузку на память. В документе утверждается, что улучшенное равномерное распределение по сравнению с MT и производительность на очень старом графическом процессоре ( Nvidia GTX260 со 192 ядрами) составляет 4,7 мс для 5 × 10 ⁷ случайных 32-битных целых чисел.

SFMT [ править ]

SFMT ( ориентированный на SIMD Fast Mersenne Twister) - это вариант Mersenne Twister, представленный в 2006 году ^[57], разработанный для обеспечения высокой скорости при работе на 128-битном SIMD.

• Это примерно в два раза быстрее, чем Mersenne Twister. ^[58]
• У него лучшее свойство равнораспределения v-битовой точности, чем у MT, но хуже, чем у WELL («Хорошо равномерно распределенная длиннопериодная линейная») .
• Он быстрее восстанавливается из начального состояния с нулевым избытком, чем MT, но медленнее, чем WELL.
• Он поддерживает различные периоды от 2 ⁶⁰⁷ −1 до 2 ²¹⁶⁰⁹¹ −1.

Intel SSE2 и PowerPC AltiVec поддерживаются SFMT. Он также используется для игр с Cell BE на PlayStation 3 . ^[59]

TinyMT [ править ]

TinyMT - это вариант Mersenne Twister, предложенный Сайто и Мацумото в 2011 году. ^[60] TinyMT использует всего 127 бит пространства состояний, что значительно меньше по сравнению с 2,5 КиБ состояния в оригинале. Однако он имеет период 2 ¹²⁷ -1, что намного короче, чем у оригинала, поэтому авторы рекомендуют его только в тех случаях, когда память находится в нехватке.

Ссылки [ править ]

Дальнейшее чтение [ править ]

• Харасе, С. (2014), «О _2- линейных отношениях генераторов псевдослучайных чисел Мерсенна Твистера», Математика и компьютеры в моделировании , 100 : 103–113, arXiv : 1301.5435 , doi : 10.1016 / j.matcom.2014.02. 002 , S2CID  6984431.
• Харасе, С. (2019), «Преобразование Mersenne Twister в числа с плавающей запятой двойной точности», Математика и компьютеры в моделировании , 161 : 76–83, arXiv : 1708.06018 , doi : 10.1016 / j.matcom.2018.08.006 , S2CID  19777310.

Внешние ссылки [ править ]

• Академическая статья для MT и статьи Макото Мацумото по теме
• Домашняя страница Mersenne Twister с кодами на C, Fortran, Java, Lisp и некоторых других языках
• Примеры Mersenne Twister - коллекция реализаций Mersenne Twister на нескольких языках программирования - на GitHub
• SFMT в действии: Часть I - Создание DLL, включая поддержку SSE2 - в Code Project