Войти
Вихрь Мерсенна является псевдослучайных чисел (ПСЧ). Это, безусловно, наиболее широко используемый ГПСЧ общего назначения. Его название происходит от того факта, что длина периода выбрана как простое число Мерсенна.
Mersenne Twister был разработан в 1997 году Макото Мацумото [ джа ] (松本 眞) и Такудзи Нисимура (西村 拓 士). Он был разработан специально для исправления большинства недостатков, обнаруженных в старых ГПСЧ.
Наиболее часто используемая версия алгоритма Мерсенна Твистера основана на простом числе Мерсенна 2 19937 -1. Стандартная реализация этого, MT19937, использует 32-битную длину слова. Существует еще одна реализация (с пятью вариантами), в которой используется длина слова 64 бита, MT19937-64; он генерирует другую последовательность.
Mersenne Twister используется в качестве ГПСЧ по умолчанию в следующем программном обеспечении:
Он также доступен в Apache Commons, в стандартном C ++ (начиная с C ++ 11 ) и в Mathematica. Надстройка на реализацию обеспечивается во многих программных библиотеках, в том числе Boost, C ++ библиотеки, в библиотеке CUDA, и численной библиотека NAG.
Mersenne Twister - один из двух PRNG в SPSS : второй генератор сохранен только для совместимости со старыми программами, а Mersenne Twister считается «более надежным». Mersenne Twister также является одним из ГПСЧ в SAS : другие генераторы устарели и устарели. Mersenne Twister - это ГПСЧ по умолчанию в Stata, другой - KISS, для совместимости со старыми версиями Stata.
Альтернативный генератор, WELL («Well Equidistributed Long-period Linear»), предлагает более быстрое восстановление, равную случайность и почти равную скорость.
Генераторы xorshift и их варианты Marsaglia являются самыми быстрыми в классе LFSR.
64-битные MELG («64-битные максимально равнораспределенные F 2 -линейные генераторы с простым периодом Мерсенна») полностью оптимизированы с точки зрения свойств k -распределения.
Семейство ACORN (опубликовано в 1989 г.) - это еще один k- распределенный ГПСЧ, который показывает скорость вычислений, аналогичную MT, и лучшие статистические свойства, поскольку он удовлетворяет всем текущим (2019 г.) критериям TestU01; при использовании с соответствующим выбором параметров ACORN может иметь произвольно длительный период и точность.
Семейство PCG - это более современный долгопериодический генератор с лучшей локализацией кэша и менее обнаруживаемым смещением при использовании современных методов анализа.
Последовательность псевдослучайных х I из W - битовых целых чисел периода Р называется к-распределенной для v точности битовое, если выполнено следующее.
Визуализация генерации псевдослучайных 32-битных целых чисел с помощью Mersenne Twister. В разделе «Извлечь число» показан пример, когда целое число 0 уже было выведено, а индекс - целое число 1. «Сгенерировать числа» запускается, когда все целые числа были выведены. Для w- битного слова Twister Мерсенна генерирует целые числа в диапазоне [0, 2 w −1].
Алгоритм Мерсенна Твистера основан на матричной линейной рекуррентности над конечным двоичным полем F 2. Алгоритм представляет собой сдвиговый регистр со скрученной обобщенной обратной связью (скрученный GFSR или TGFSR) рациональной нормальной формы (TGFSR (R)) с отражением и темперированием битов состояния. Основная идея состоит в том, чтобы определить ряд x i через простое рекуррентное соотношение, а затем вывести числа в форме x i T, где T - обратимая F 2 -матрица, называемая матрицей темперирования.
Общий алгоритм характеризуется следующими величинами (некоторые из этих объяснений имеют смысл только после прочтения остальной части алгоритма):
с ограничением, что 2 nw - r - 1 - простое число Мерсенна. Этот выбор упрощает тест на примитивность и тест k- распределения, которые необходимы при поиске параметров.
Ряд x определяется как ряд w -битных величин с рекуррентным соотношением:
где означает конкатенацию битовых векторов (с верхними битами слева), ⊕ побитовое исключающее ИЛИ (XOR), x k u означает верхние w - r битов x k, а x k +1 l означает младшие r битов х к +1. Преобразование скручивания A определяется в рациональной нормальной форме как:
с I w −1 в качестве единичной матрицы ( w - 1) × ( w - 1). Преимущество рациональной нормальной формы состоит в том, что умножение на A может быть эффективно выражено как: (помните, что здесь умножение матриц выполняется в F 2, и поэтому побитовое исключающее ИЛИ заменяет сложение)
где x 0 - бит младшего разряда x.
Как и TGFSR (R), Mersenne Twister каскадируется с преобразованием темперирования, чтобы компенсировать уменьшенную размерность равнораспределения (из-за выбора A в рациональной нормальной форме). Обратите внимание, что это эквивалентно использованию матрицы A, где A = T −1 AT для T - обратимой матрицы, и поэтому анализ характеристического полинома, упомянутый ниже, все еще сохраняется.
Как и в случае с A, мы выбираем преобразование темперирования, чтобы оно было легко вычислимым, и поэтому на самом деле не конструируем само T. В случае Mersenne Twister закалка определяется как
где x - следующее значение из ряда, y - временное промежуточное значение, z - значение, возвращаемое алгоритмом, с ≪, ≫ как побитовые сдвиги влево и вправо, а amp; как побитовые и. Первое и последнее преобразования добавляются для улучшения равнораспределения младших битов. Из свойства TGFSR, s + t ≥ w / 2⌋ - 1 требуется для достижения верхней границы равнораспределения для верхних битов.
Коэффициенты для MT19937:
Обратите внимание, что 32-битные реализации Mersenne Twister обычно имеют d = FFFFFFFF 16. В результате d иногда опускается в описании алгоритма, поскольку побитовое и с d в этом случае не имеет никакого эффекта.
Коэффициенты для MT19937-64:
Состояние, необходимое для реализации Mersenne Twister, представляет собой массив из n значений по w бит каждое. Для инициализации массива используется w- битное начальное значение для предоставления от x 0 до x n −1 путем установки x 0 на начальное значение и последующей установки
для i от 1 до n - 1. Первое значение, которое затем генерирует алгоритм, основано на x n, а не на x 0. Константа f формирует еще один параметр генератора, но не является частью самого алгоритма. Значение f для MT19937 составляет 1812433253, а для MT19937-64 - 6364136223846793005.
Для того, чтобы достичь 2 NW - г - 1 теоретический верхний предел периода Т ДГФС, φ В ( т) должен быть примитивный многочлен, φ B ( т), являющийся характеристический полином из
Преобразование скручивания улучшает классический GFSR со следующими ключевыми свойствами:
Следующий псевдокод реализует общий алгоритм Мерсенна Твистера. Константы w, n, m, r, a, u, d, s, b, t, c, l и f такие же, как в описании алгоритма выше. Предполагается, что int представляет тип, достаточный для хранения значений с w битами:
// Create a length n array to store the state of the generator int[0..n-1] MT int index := n+1 const int lower_mask = (1 lt;lt; r) - 1 // That is, the binary number of r 1's const int upper_mask = lowest w bits of ( not lower_mask) // Initialize the generator from a seed function seed_mt(int seed) { index := n MT[0] := seed for i from 1 to (n - 1) { // loop over each element MT[i] := lowest w bits of (f * (MT[i-1] xor (MT[i-1] gt;gt; (w-2))) + i) } } // Extract a tempered value based on MT[index] // calling twist() every n numbers function extract_number() { if index gt;= n { if index gt; n { error "Generator was never seeded" // Alternatively, seed with constant value; 5489 is used in reference C code } twist() } int y := MT[index] y := y xor ((y gt;gt; u) and d) y := y xor ((y lt;lt; s) and b) y := y xor ((y lt;lt; t) and c) y := y xor (y gt;gt; l) index := index + 1 return lowest w bits of (y) } // Generate the next n values from the series x_i function twist() { for i from 0 to (n-1) { int x := (MT[i] and upper_mask) + (MT[(i+1) mod n] and lower_mask) int xA := x gt;gt; 1 if (x mod 2) != 0 { // lowest bit of x is 1 xA := xA xor a } MT[i] := MT[(i + m) mod n] xor xA } index := 0 }
CryptMT - это потоковый шифр и криптографически безопасный генератор псевдослучайных чисел, который внутренне использует Mersenne Twister. Его разработали Мацумото и Нисимура вместе с Марико Хагита и Муцуо Сайто. Он был отправлен в проект eSTREAM сети eCRYPT. В отличие от Mersenne Twister или других его производных, CryptMT запатентован.
MTGP - это вариант Mersenne Twister, оптимизированный для графических процессоров, опубликованный Муцуо Сайто и Макото Мацумото. Базовые операции линейной рекурсии расширены из MT, и параметры выбраны, чтобы позволить многим потокам вычислять рекурсию параллельно, совместно используя свое пространство состояний для уменьшения нагрузки на память. В документе утверждается, что улучшенное равнораспределение по сравнению с MT и производительность на очень старом графическом процессоре ( Nvidia GTX260 со 192 ядрами) составляет 4,7 мс для 5 × 10 7 случайных 32-битных целых чисел.
SFMT ( ориентированный на SIMD Fast Mersenne Twister) - это вариант Mersenne Twister, представленный в 2006 году, разработанный, чтобы быть быстрым при работе на 128-битном SIMD.
Intel SSE2 и PowerPC AltiVec поддерживаются SFMT. Он также используется для игр с Cell BE на PlayStation 3.
TinyMT - это вариант Mersenne Twister, предложенный Сайто и Мацумото в 2011 году. TinyMT использует всего 127 бит пространства состояний, что значительно меньше по сравнению с 2,5 КиБ состояния оригинала. Однако он имеет период 2 127 -1, что намного короче, чем у оригинала, поэтому авторы рекомендуют его только в тех случаях, когда память находится в нехватке.
.
.