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

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

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

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

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

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

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

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

${\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)}$.

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

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

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

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

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

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

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

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

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

${\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 }$ ${\displaystyle x_{k}^{u}}$ ${\displaystyle x_{k}}$ ${\displaystyle x_{k+1}^{l}}$ ${\displaystyle x_{k+1}}$

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

${\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 }$

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

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

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

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

${\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 требуется достичь верхней границы равномерного распределения для верхних бит. ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle \ll }$ ${\displaystyle \gg }$ ${\displaystyle \&}$ ${\displaystyle s+t\geq \left\lfloor {\frac {w}{2}}\right\rfloor -1}$

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

${\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]

${\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 бит для подачи через установку начального значения и последующую установку ${\displaystyle x_{0}}$ ${\displaystyle x_{n-1}}$ ${\displaystyle x_{0}}$

${\displaystyle x_{i}=f\times (x_{i-1}\oplus (x_{i-1}\gg (w-2)))+i}$

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

• Первое значение, которое генерирует алгоритм, основано на , а не на . ${\displaystyle x_{n}}$ ${\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 , должен быть примитивным многочленом , являющимся характеристическим многочленом ${\displaystyle 2^{nw-r}-1}$ ${\displaystyle \phi _{B}(t)}$ ${\displaystyle \phi _{B}(t)}$

${\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}}}$

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

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

• Период достигает теоретического верхнего предела (за исключением случая, когда он инициализирован значением 0) ${\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 ⁷ случайных 32-битных целых чисел.

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

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

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

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

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

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

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

Недостатки:

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

Приложения

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

• Языки программирования: Dyalog APL , ^[21] IDL , ^[22] R , ^[23] Ruby , ^[24] Free Pascal , ^[25] PHP , ^[26] Python (также доступен в NumPy , однако с версии 1.17 значение по умолчанию было изменено на PCG64 ^[27] ), ^{[28] [29] [30]} CMU Common Lisp , ^[31] Embeddable Common Lisp , ^[32] Steel Bank Common Lisp , ^[33] Julia (до Julia 1.6 LTS, все еще доступен в более поздних версиях, но с версии 1.7 по умолчанию используется более качественный/быстрый ГСЧ) ^[34]
• Unix-подобные библиотеки и программное обеспечение: GLib , ^[35] GNU Multiple Precision Arithmetic Library , ^[36] GNU Octave , ^[37] GNU Scientific Library ^[38]
• Другое: Microsoft Excel , ^[39] GAUSS , ^[40] gretl , ^[41] Stata , ^[42] SageMath , ^[43] Scilab , ^[44] Maple , ^[45] MATLAB ^[46]

Он также доступен в 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] ${\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. "std::mersenne_twister_engine". Генерация псевдослучайных чисел . Получено 2015-07-20 .
6. "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. P. L'Ecuyer и R. Simard, "TestU01: "Библиотека AC для эмпирического тестирования генераторов случайных чисел", ACM Transactions on Mathematical Software , 33, 4, статья 22 (август 2007 г.).
14. Примечание: 2 ¹⁹⁹³⁷ приблизительно равно 4,3 × 10 ⁶⁰⁰¹ ; это на много порядков больше предполагаемого числа частиц в наблюдаемой Вселенной , которое составляет 10 ⁸⁷ .
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". Генерация псевдослучайных чисел . Получено 2012-09-25 .
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 ${\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