Мерсенн Твистер
Генератор псевдослучайных чисел

Mersenne Twister — это генератор псевдослучайных чисел общего назначения (PRNG), разработанный в 1997 году Макото Мацумото (松本 眞) и Такудзи Нишимурой (西村 拓士) . [1] [2] Его название происходит от выбора простого числа Мерсенна в качестве длины периода.

Вихрь Мерсенна был специально разработан для исправления большинства недостатков, обнаруженных в старых ГПСЧ.

Наиболее часто используемая версия алгоритма Mersenne Twister основана на простом числе Мерсенна . Стандартная реализация этого, MT19937, использует 32-битную длину слова. Существует другая реализация (с пятью вариантами [3] ), которая использует 64-битную длину слова, MT19937-64; она генерирует другую последовательность. 2 19937 − 1 {\displaystyle 2^{19937}-1}

к-распределение

Псевдослучайная последовательность w -битных целых чисел периода P называется k-распределенной с точностью v -бит, если выполняется следующее. х я {\displaystyle x_{i}}

Пусть trunc v ( x ) обозначает число, образованное ведущими v битами x , и рассмотрим P из k v -битных векторов
( ствол в ⁡ ( х я ) , ствол в ⁡ ( х я + 1 ) , … , ствол в ⁡ ( х я + к − 1 ) ) ( 0 ≤ я < П ) {\displaystyle (\operatorname {trunc} _{v}(x_{i}),\operatorname {trunc} _{v}(x_{i+1}),\,\ldots ,\operatorname {trunc} _{v}(x_{i+k-1}))\quad (0\leq i<P)} .
Тогда каждая из возможных комбинаций битов встречается одинаковое количество раз за период, за исключением комбинации, состоящей из одних нулей, которая встречается на один раз реже. 2 к в {\displaystyle 2^{кв}}

Алгоритмическая детализация

Визуализация генерации псевдослучайных 32-битных целых чисел с использованием Mersenne Twister. Раздел «Извлечение числа» показывает пример, где целое число 0 уже было выведено, а индекс равен целому числу 1. «Генерация чисел» запускается, когда все целые числа были выведены.

Для слова длиной w бит алгоритм Mersenne Twister генерирует целые числа в диапазоне . [ 0 , 2 ж − 1 ] {\displaystyle [0,2^{w}-1]}

Алгоритм Mersenne Twister основан на матричной линейной рекуррентности над конечным двоичным полем . Алгоритм представляет собой скрученный обобщенный регистр сдвига с обратной связью [4] (скрученный GFSR или TGFSR) рациональной нормальной формы (TGFSR(R)), с отражением бита состояния и закалкой. Основная идея заключается в определении ряда через простое рекуррентное соотношение, а затем выводе чисел вида , где T — обратимая -матрица, называемая матрицей закалки . Ф 2 {\displaystyle {\textbf {F}}_{2}} x i {\displaystyle x_{i}} x i T {\displaystyle x_{i}^{T}} F 2 {\displaystyle {\textbf {F}}_{2}}

Общий алгоритм характеризуется следующими величинами:

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

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

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

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

где обозначает конкатенацию битовых векторов (со старшими битами слева), побитовое исключающее ИЛИ (XOR), означает старшие w − r битов , а означает младшие r битов . ∣ {\displaystyle \mid } ⊕ {\displaystyle \oplus } x k u {\displaystyle x_{k}^{u}} x k {\displaystyle x_{k}} x k + 1 l {\displaystyle x_{k+1}^{l}} x k + 1 {\displaystyle x_{k+1}}

Все индексы могут быть смещены на -n

x k := x k − ( n − m ) ⊕ ( ( x k − n u ∣ x k − ( n − 1 ) l ) A ) k = n , n + 1 , n + 2 , … {\displaystyle x_{k}:=x_{k-(n-m)}\oplus \left(({x_{k-n}}^{u}\mid {x_{k-(n-1)}}^{l})A\right)\qquad k=n,n+1,n+2,\ldots }

где теперь левая ось, , является следующим сгенерированным значением в ряду с точки зрения значений, сгенерированных в прошлом, которые находятся в правой оси. x k {\displaystyle x_{k}}

Преобразование скручивания A определяется в рациональной нормальной форме как: с единичной матрицей. Рациональная нормальная форма имеет то преимущество, что умножение на A может быть эффективно выражено как: (помните, что здесь умножение матриц выполняется в , и поэтому побитовое XOR заменяет сложение) где — младший бит . A = ( 0 I w − 1 a w − 1 ( a w − 2 , … , a 0 ) ) {\displaystyle A={\begin{pmatrix}0&I_{w-1}\\a_{w-1}&(a_{w-2},\ldots ,a_{0})\end{pmatrix}}} I w − 1 {\displaystyle I_{w-1}} ( w − 1 ) ( w − 1 ) {\displaystyle (w-1)(w-1)} F 2 {\displaystyle {\textbf {F}}_{2}} x A = { x ≫ 1 x 0 = 0 ( x ≫ 1 ) ⊕ a x 0 = 1 {\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 0 {\displaystyle x_{0}} x {\displaystyle x}

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

Как и в случае с A , мы выбираем преобразование закалки, которое легко вычисляется, и поэтому фактически не конструируем само T. Это закалка определяется в случае вихря Мерсенна как

y ≡ x ⊕ ( ( x ≫ u )   &   d ) y ≡ y ⊕ ( ( y ≪ s )   &   b ) y ≡ y ⊕ ( ( y ≪ t )   &   c ) z ≡ y ⊕ ( y ≫ l ) {\displaystyle {\begin{aligned}y&\equiv x\oplus ((x\gg u)~\And ~d)\\y&\equiv y\oplus ((y\ll s)~\And ~b)\\y&\equiv y\oplus ((y\ll t)~\And ~c)\\z&\equiv y\oplus (y\gg l)\end{aligned}}}

где — следующее значение из ряда, — временное промежуточное значение, а — значение, возвращаемое алгоритмом, с и как побитовые сдвиги влево и вправо , и как побитовое И. Первое и последнее преобразования добавляются для улучшения равномерного распределения нижних бит. Из свойства TGFSR требуется достичь верхней границы равномерного распределения для верхних бит. x {\displaystyle x} y {\displaystyle y} z {\displaystyle z} ≪ {\displaystyle \ll } ≫ {\displaystyle \gg } & {\displaystyle \&} s + t ≥ ⌊ w 2 ⌋ − 1 {\displaystyle s+t\geq \left\lfloor {\frac {w}{2}}\right\rfloor -1}

Коэффициенты для MT19937 следующие:

( w , n , m , r ) = ( 32 , 624 , 397 , 31 ) a = 9908B0DF 16 ( u , d ) = ( 11 , FFFFFFFF 16 ) ( s , b ) = ( 7 , 9D2C5680 16 ) ( t , c ) = ( 15 , EFC60000 16 ) l = 18 {\displaystyle {\begin{aligned}(w,n,m,r)&=(32,624,397,31)\\a&={\textrm {9908B0DF}}_{16}\\(u,d)&=(11,{\textrm {FFFFFFFF}}_{16})\\(s,b)&=(7,{\textrm {9D2C5680}}_{16})\\(t,c)&=(15,{\textrm {EFC60000}}_{16})\\l&=18\\\end{aligned}}}

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

Коэффициенты для MT19937-64 следующие: [5]

( w , n , m , r ) = ( 64 , 312 , 156 , 31 ) a = B5026F5AA96619E9 16 ( u , d ) = ( 29 , 5555555555555555 16 ) ( s , b ) = ( 17 , 71D67FFFEDA60000 16 ) ( t , c ) = ( 37 , FFF7EEE000000000 16 ) l = 43 {\displaystyle {\begin{aligned}(w,n,m,r)=(64,312,156,31)\\a={\textrm {B5026F5AA96619E9}}_{16}\\(u,d)=(29,{\textrm {5555555555555555}}_{16})\\(s,b)=(17,{\textrm {71D67FFFEDA60000}}_{16})\\(t,c)=(37,{\textrm {FFF7EEE000000000}}_{16})\\l=43\\\end{aligned}}}

Инициализация

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

x i = f × ( x i − 1 ⊕ ( x i − 1 ≫ ( w − 2 ) ) ) + i {\displaystyle x_{i}=f\times (x_{i-1}\oplus (x_{i-1}\gg (w-2)))+i}

для с по . i {\displaystyle i} 1 {\displaystyle 1} n − 1 {\displaystyle n-1}

  • Первое значение, которое генерирует алгоритм, основано на , а не на . x n {\displaystyle x_{n}} x 0 {\displaystyle x_{0}}
  • Константа f является еще одним параметром генератора, хотя и не является частью самого алгоритма.
  • Значение f для MT19937 равно 1812433253.
  • Значение f для MT19937-64 равно 6364136223846793005. [5]

код С

#include <stdint.h> #define n 624 #define m 397 #define w 32 #define r 31 #define UMASK (0xffffffffUL << r) #define LMASK (0xffffffffUL >> (wr)) #define a 0x9908b0dfUL #define u 11 #define s 7 #define t 15 #define l 18 #define b 0x9d2c5680UL #define c 0xefc60000UL #define f 1812433253ULtypedef struct { uint32_t state_array [ n ]; // массив для вектора состояния int state_index ; // индекс в массиве векторов состояния, 0 <= state_index <= n-1 всегда } mt_state ;        void initialize_state ( mt_state * state , uint32_t seed ) { uint32_t * state_array = & ( state -> state_array [ 0 ]); state_array [ 0 ] = seed ; // предлагаемое начальное seed = 19650218UL for ( int i = 1 ; i < n ; i ++ ) { seed = f * ( seed ^ ( seed >> ( w -2 ))) + i ; // Knuth TAOCP Vol2. 3rd Ed. P.106 для множителя. state_array [ i ] = seed ; } state -> state_index = 0 ; }                                          uint32_t random_uint32 ( mt_state * state ) { uint32_t * state_array = & ( state -> state_array [ 0 ]); int k = state -> state_index ; // указывает на текущее местоположение состояния // 0 <= state_index <= n-1 всегда // int k = k - n; // указывает на состояние за n итераций до // if (k < 0) k += n; // циклическая индексация по модулю n // предыдущие 2 строки на самом деле ничего не делают // только для иллюстрации int j = k - ( n -1 ); // указывает на состояние за n-1 итераций до if ( j < 0 ) j += n ; // циклическая индексация по модулю n                                 uint32_t x = ( state_array [ k ] & UMASK ) | ( state_array [ j ] & LMASK ); uint32_t xA = x >> 1 ; if ( x & 0x00000001UL ) xA ^= a ; j = k - ( n - m ); // указать на состояние за nm итераций до этого if ( j < 0 ) j += n ; // циклическая индексация по модулю n x = state_array [ j ] ^ xA ; // вычислить следующее значение в состоянии state_array [ k ++ ] = x ; // обновить новое значение состояния if ( k >= n ) k = 0 ; // циклическая индексация по модулю n state -> state_index = k ; uint32_t y = x ^ ( x >> u ); // закалка y = y ^ (( y << s ) & b ); y = y ^ (( y << t ) & c ); uint32_t z = y ^ ( y >> l ); return z ; }

Сравнение с классическим GFSR

Для достижения теоретического верхнего предела периода в T GFSR , должен быть примитивным многочленом , являющимся характеристическим многочленом 2 n w − r − 1 {\displaystyle 2^{nw-r}-1} ϕ B ( t ) {\displaystyle \phi _{B}(t)} ϕ B ( t ) {\displaystyle \phi _{B}(t)}

B = ( 0 I w ⋯ 0 0 ⋮ I w ⋮ ⋱ ⋮ ⋮ ⋮ 0 0 ⋯ I w 0 0 0 ⋯ 0 I w − r S 0 ⋯ 0 0 ) ← m -th row {\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{\text{-th row}}\\\\\\\\\end{matrix}}}
S = ( 0 I r I w − r 0 ) A {\displaystyle S={\begin{pmatrix}0&I_{r}\\I_{w-r}&0\end{pmatrix}}A}

Трансформация кручения улучшает классический GFSR, придавая ему следующие ключевые свойства:

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

Варианты

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

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

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

  • Он примерно в два раза быстрее, чем вихрь Мерсенна. [10]
  • Он имеет лучшее свойство равномерного распределения точности v-бит, чем MT, но худшее, чем WELL («Well Equidistributed Long-period Linear») .
  • Он быстрее восстанавливается из исходного состояния с нулевым избытком, чем MT, но медленнее, чем WELL.
  • Поддерживает различные периоды от 2 607  − 1 до 2 216091  − 1.

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

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

Характеристики

Преимущества:

  • Разрешительно-лицензируемый и не имеющий патентов для всех вариантов, кроме CryptMT.
  • Проходит многочисленные тесты на статистическую случайность, включая тесты Diehard и большинство, но не все, тестов TestU01 . [13]
  • Очень долгий период . Обратите внимание, что хотя долгий период не является гарантией качества генератора случайных чисел, короткие периоды, такие как распространенные во многих старых пакетах программного обеспечения, могут быть проблематичными. [14] 2 19937 − 1 {\displaystyle 2^{19937}-1} 2 32 {\displaystyle 2^{32}}
  • k-распределенный с точностью 32 бита для каждого 1 ≤ k ≤ 623 {\displaystyle 1\leq k\leq 623}
  • Реализации обычно создают случайные числа быстрее, чем аппаратно реализованные методы. Исследование показало, что Mersenne Twister создает 64-битные плавающие случайные числа примерно в двадцать раз быстрее, чем аппаратно реализованный процессорный набор инструкций RDRAND . [15]

Недостатки:

  • Относительно большой буфер состояний, почти 2,5  КБ , если не используется вариант TinyMT.
  • Посредственная пропускная способность по современным стандартам, если только не используется вариант SFMT (обсуждаемый ниже). [16]
  • Демонстрирует два явных провала (линейная сложность) в Crush и BigCrush в наборе TestU01. Тест, как и Mersenne Twister, основан на -алгебре . [13] F 2 {\displaystyle {\textbf {F}}_{2}}
  • Несколько экземпляров, которые отличаются только начальным значением (но не другими параметрами), обычно не подходят для моделирования Монте-Карло , требующего независимых генераторов случайных чисел, хотя существует метод выбора нескольких наборов значений параметров. [17] [18]
  • Плохая диффузия: может потребоваться много времени, чтобы начать генерировать выходные данные, которые проходят тесты на случайность , если начальное состояние в высшей степени неслучайно — особенно если в начальном состоянии много нулей. Следствием этого является то, что два экземпляра генератора, запущенные с начальными состояниями, которые почти одинаковы, обычно выводят почти одну и ту же последовательность для многих итераций, прежде чем в конечном итоге расходятся. Обновление алгоритма MT 2002 года улучшило инициализацию, так что начало с такого состояния очень маловероятно. [19] Говорят, что версия GPU (MTGP) еще лучше. [20]
  • Содержит подпоследовательности с большим количеством нулей, чем единиц. Это усугубляет плохие свойства диффузии, затрудняя восстановление из состояний с множеством нулей.
  • Не является криптографически безопасным , если только не используется вариант CryptMT (обсуждаемый ниже). Причина в том, что наблюдение достаточного количества итераций (624 в случае MT19937, поскольку это размер вектора состояния, из которого производятся будущие итерации) позволяет предсказать все будущие итерации.

Приложения

Mersenne Twister используется в качестве ГПСЧ по умолчанию в следующем программном обеспечении:

Он также доступен в Apache Commons , [47] в стандартной библиотеке C++ (начиная с C++11 ), [48] [49] и в Mathematica . [50] Дополнительные реализации предоставляются во многих библиотеках программ, включая Boost C++ Libraries , [51] CUDA Library , [52] и NAG Numerical Library . [53]

Mersenne Twister — один из двух PRNG в SPSS : другой генератор оставлен только для совместимости со старыми программами, а Mersenne Twister заявлен как «более надежный». [54] Mersenne Twister — это также один из PRNG в SAS : другие генераторы устарели и устарели. [55] Mersenne Twister — это PRNG по умолчанию в Stata , другой — KISS , для совместимости со старыми версиями Stata. [56]

Альтернативы

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

Генераторы и варианты xorshift Марсальи являются самыми быстрыми в классе LFSR. [58]

64-битные MELG («64-битные максимально равнораспределенные линейные генераторы с простым периодом Мерсенна») полностью оптимизированы с точки зрения свойств k -распределения. [59] F 2 {\displaystyle {\textbf {F}}_{2}}

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

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

Ссылки

  1. ^ Мацумото, М.; Нисимура, Т. (1998). «Вихрь Мерсенна: 623-мерно равнораспределенный равномерный генератор псевдослучайных чисел». Труды ACM по моделированию и компьютерному моделированию . 8 (1): 3– 30. CiteSeerX  10.1.1.215.1141 . doi :10.1145/272991.272995. S2CID  3332028.
  2. ^ Например, Марсланд С. (2011) Машинное обучение ( CRC Press ), §4.1.1. Также см. раздел «Внедрение в программные системы».
  3. ^ Джон Савард. "Вихрь Мерсенна". Последующая статья, опубликованная в 2000 году, дала пять дополнительных форм вихря Мерсенна с периодом 2^19937-1. Все пять были разработаны для реализации с 64-битной арифметикой вместо 32-битной.
  4. ^ Мацумото, М.; Курита, И. (1992). «Скрученные генераторы GFSR». Труды ACM по моделированию и компьютерному моделированию . 2 (3): 179– 194. doi :10.1145/146382.146383. S2CID  15246234.
  5. ^ ab "std::mersenne_twister_engine". Генерация псевдослучайных чисел . Получено 2015-07-20 .
  6. ^ ab "CryptMt and Fubuki". eCRYPT . Архивировано из оригинала 2012-07-01 . Получено 2017-11-12 .
  7. ^ Мацумото, Макото; Нисимура, Такудзи; Хагита, Марико; Сайто, Муцуо (2005). «Криптографический поток Мерсенна и блочный шифр Фубуки» (PDF) .
  8. ^ Муцуо Сайто; Макото Мацумото (2010). «Варианты вихря Мерсенна, подходящие для графических процессоров». arXiv : 1005.4973v3 [cs.MS].
  9. ^ "SIMD-ориентированный быстрый вихрь Мерсенна (SFMT)". hiroshima-u.ac.jp . Получено 4 октября 2015 г. .
  10. ^ "SFMT:Сравнение скорости". hiroshima-u.ac.jp . Получено 4 октября 2015 г. .
  11. ^ "PlayStation3 License". scei.co.jp . Получено 4 октября 2015 г. .
  12. ^ "Tiny Mersenne Twister (TinyMT)". hiroshima-u.ac.jp . Получено 4 октября 2015 г. .
  13. ^ ab P. L'Ecuyer и R. Simard, "TestU01: "Библиотека AC для эмпирического тестирования генераторов случайных чисел", ACM Transactions on Mathematical Software , 33, 4, статья 22 (август 2007 г.).
  14. ^ Примечание: 2 19937 приблизительно равно 4,3 × 10 6001 ; это на много порядков больше предполагаемого числа частиц в наблюдаемой Вселенной , которое составляет 10 87 .
  15. ↑ Route, Matthew (10 августа 2017 г.). «Синтез популяции сверххолодных карликов в радиоизлучении». The Astrophysical Journal . 845 (1): 66. arXiv : 1707.02212 . Bibcode : 2017ApJ...845...66R. doi : 10.3847/1538-4357/aa7ede . S2CID  118895524.
  16. ^ "SIMD-ориентированный быстрый вихрь Мерсенна (SFMT): в два раза быстрее, чем вихрь Мерсенна". Японское общество содействия науке . Получено 27 марта 2017 г.
  17. ^ Макото Мацумото; Такудзи Нисимура. «Динамическое создание генераторов псевдослучайных чисел» (PDF) . Получено 19 июля 2015 г.
  18. ^ Хироши Харамото; Макото Мацумото; Такудзи Нисимура; Франсуа Паннетон; Пьер Л'Экюйер. "Эффективный прыжок вперед для F2-линейных генераторов случайных чисел" (PDF) . Получено 12 ноября 2015 г.
  19. ^ "mt19937ar: Mersenne Twister с улучшенной инициализацией". hiroshima-u.ac.jp . Получено 4 октября 2015 г. .
  20. ^ Фог, Агнер (1 мая 2015 г.). «Генератор псевдослучайных чисел для векторных процессоров и многоядерных процессоров». Журнал современных прикладных статистических методов . 14 (1): 308–334 . doi : 10.22237/jmasm/1430454120 .
  21. ^ "Случайная ссылка". Справочное руководство по языку Dyalog . Получено 04.06.2020 .
  22. ^ "RANDOMU (Справочник IDL)". Центр документов Exelis VIS . Получено 23.08.2013 .
  23. ^ "Генератор случайных чисел". CRAN Task View: Распределения вероятностей . Получено 29.05.2012 .
  24. ^ "Документация класса "Random"". Документация Ruby 1.9.3 . Получено 29.05.2012 .
  25. ^ "random". бесплатная документация pascal . Получено 28.11.2013 .
  26. ^ "mt_rand — Генерация лучшего случайного значения". PHP Manual . Получено 2016-03-02 .
  27. ^ "Заметки о выпуске NumPy 1.17.0 — Руководство NumPy v1.21". numpy.org . Получено 29.06.2021 .
  28. ^ "9.6 random — Генерация псевдослучайных чисел". Документация Python v2.6.8 . Получено 29.05.2012 .
  29. ^ "8.6 random — Генерация псевдослучайных чисел". Документация Python v3.2 . Получено 29.05.2012 .
  30. ^ "random — Генерация псевдослучайных чисел — Документация Python 3.8.3". Документация Python 3.8.3 . Получено 2020-06-23 .
  31. ^ "Выбор дизайна и расширения". Руководство пользователя CMUCL . Получено 2014-02-03 .
  32. ^ "Случайные состояния". Руководство ECL . Получено 2015-09-20 .
  33. ^ "Генерация случайных чисел". Руководство пользователя SBCL .
  34. ^ "Случайные числа · Язык Джулии". docs.julialang.org . Получено 21.06.2022 .
  35. ^ «Случайные числа: Справочное руководство по GLib».
  36. ^ "Алгоритмы случайных чисел". GNU MP . Получено 21.11.2013 .
  37. ^ "16.3 Специальные вспомогательные матрицы". GNU Octave . Встроенная функция: rand
  38. ^ "Случайные числовые переменные среды". GNU Scientific Library . Получено 24.11.2013 .
  39. ^ Мелард, Г. (2014), «О точности статистических процедур в Microsoft Excel 2010», Computational Statistics , 29 (5): 1095–1128 , CiteSeerX 10.1.1.455.5508 , doi :10.1007/s00180-014-0482-5, S2CID  54032450 .
  40. ^ «Справочник языка GAUSS 14» (PDF) .
  41. ^ "uniform". Справочник функций Gretl .
  42. ^ «Новый генератор случайных чисел — 64-битный вихрь Мерсенна».
  43. ^ «Распределения вероятностей — Справочное руководство Sage v7.2: Вероятность».
  44. ^ "grand - Случайные числа". Справка Scilab .
  45. ^ "генератор случайных чисел". Maple Online Help . Получено 21.11.2013 .
  46. ^ "Алгоритмы генератора случайных чисел". Центр документации, MathWorks .
  47. ^ "Генерация данных". Руководство пользователя Apache Commons Math .
  48. ^ "Генерация случайных чисел в C++11" (PDF) . Standard C++ Foundation .
  49. ^ "std::mersenne_twister_engine". Генерация псевдослучайных чисел . Получено 25.09.2012 .
  50. ^ [1] Документация Mathematica
  51. ^ "boost/random/mersenne_twister.hpp". Библиотеки Boost C++ . Получено 29-05-2012 .
  52. ^ "Обзор API хоста". Документация по инструментарию CUDA . Получено 2016-08-02 .
  53. ^ "G05 – Генераторы случайных чисел". Введение в главу библиотеки NAG . Получено 29.05.2012 .
  54. ^ "Генератор случайных чисел". IBM SPSS Statistics . Получено 21.11.2013 .
  55. ^ "Использование функций случайных чисел". Справочник языка SAS . Получено 21.11.2013 .
  56. ^ Справка по Stata: set rng -- Установить, какой генератор случайных чисел (ГСЧ) использовать
  57. ^ П. Л'Экуайе, «Генератор случайных чисел с равномерным распределением», Международная энциклопедия статистической науки , Ловрич, Миодраг (ред.), Springer-Verlag, 2010.
  58. ^ "Генератор xorshift*/xorshift+ и перестрелка с PRNG".
  59. ^ Харасе, С.; Кимото, Т. (2018). «Реализация 64-битных максимально равнораспределенных F2-линейных генераторов с простым периодом Мерсенна». Труды ACM по математическому программному обеспечению . 44 (3): 30:1–30:11. arXiv : 1505.06582 . doi : 10.1145/3159444. S2CID  14923086.
  60. ^ "The PCG Paper". 27 июля 2017 г.

Дальнейшее чтение

  • Харас, С. (2014), «О -линейных отношениях генераторов псевдослучайных чисел Mersenne Twister», Математика и компьютеры в моделировании , 100 : 103–113 , arXiv : 1301.5435 , doi : 10.1016/j.matcom.2014.02.002, S2CID  6984431 F 2 {\displaystyle \mathbb {F} _{2}} .
  • Харас, С. (2019), «Преобразование вихря Мерсенна в числа с плавающей точкой двойной точности», Математика и компьютеры в моделировании , 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
Retrieved from "https://en.wikipedia.org/w/index.php?title=Mersenne_Twister&oldid=1266817354"