Введение
Генератор псевдослучайных чисел
Алгоритм Mersenne Twister – это генератор псевдослучайных чисел (PRNG) общего назначения, разработанный в 1997 году и Такудзи Нисимурой (西村 拓士). Свое название он получил благодаря выбору простого числа Мерсена в качестве длины периода. Mersenne Twister был разработан специально для устранения большинства недостатков, выявленных в более ранних PRNG. Наиболее часто используемая версия алгоритма Mersenne Twister основана на простом числе Мерсена. Стандартная реализация, MT19937, использует 32-битную длину слова. Существует также другая реализация (с пятью вариантами), использующая 64-битную длину слова, MT19937 64; она генерирует иную последовательность.
Инициализация
Состояние, необходимое для реализации Mersenne Twister, представляет собой массив из n значений, каждое из которых занимает w бит. Для инициализации массива используется начальное значение (seed) размером w бит, которое передается путем установки первого элемента массива в это значение, а затем установки остальных элементов от до . Первое значение, которое генерирует алгоритм, основано на , а не на . Константа f является еще одним параметром генератора, хотя и не является частью самого алгоритма. Значение f для MT19937 равно 1812433253. Значение f для MT19937 64 равно 6364136223846793005. Он был разработан Мацумото и Нисимурой совместно с Марико Хагита и Муцуо Сайто. Он был представлен проекту eSTREAM сети eCRYPT. Основные операции линейной рекурсии расширены по сравнению с MT, а параметры выбраны таким образом, чтобы позволить нескольким потокам вычислять рекурсию параллельно, совместно используя пространство состояний для снижения нагрузки на память. В статье утверждается, что улучшено равномерное распределение по сравнению с MT и достигнута производительность 4,7 мс для 5 × 107 случайных 32-битных целых чисел на старом графическом процессоре (Nvidia GTX260 с 192 ядрами) образца 2008 года. SFMT (SIMD-ориентированный Fast Mersenne Twister) — это вариант Mersenne Twister, представленный в 2006 году и разработанный для высокой скорости работы на 128-битной SIMD-архитектуре. Он примерно в два раза быстрее, чем Mersenne Twister. Он обладает лучшими свойствами равномерного распределения с точностью v бит по сравнению с MT, но худшими, чем у WELL ("Well Equidistributed Long period Linear"). Он быстрее восстанавливается из начального состояния с нулевым избытком, чем MT, но медленнее, чем WELL. Он поддерживает различные периоды от 2607 − 1 до 2216091 − 1. SFMT поддерживается Intel SSE2 и PowerPC AltiVec. Он также используется в играх на Cell BE в PlayStation 3. TinyMT — это вариант Mersenne Twister, предложенный Сайто и Мацумото в 2011 году. TinyMT использует всего 127 бит пространства состояний, что значительно меньше, чем у оригинала, который требует 2,5 КБ. Однако его период равен , что значительно короче, чем у оригинала, поэтому авторы рекомендуют его использовать только в случаях, когда память ограничена.
for from to
The first value the algorithm then generates is based on , not on The constant f forms another parameter to the generator, though not part of the algorithm proper. The value for f for MT19937 is 1812433253. The value for f for MT19937 64 is 6364136223846793005. It was developed by Matsumoto and Nishimura alongside Mariko Hagita and Mutsuo Saito. It has been submitted to the eSTREAM project of the eCRYPT network. The basic linear recurrence operations are extended from MT and parameters are chosen to allow many threads to compute the recursion in parallel, while sharing their state space to reduce memory load. The paper claims improved equidistribution over MT and performance on an old (2008 era) GPU (Nvidia GTX260 with 192 cores) of 4.7 ms for 5×107 random 32 bit integers. The SFMT (SIMD oriented Fast Mersenne Twister) is a variant of Mersenne Twister, introduced in 2006, designed to be fast when it runs on 128 bit SIMD. It is roughly twice as fast as Mersenne Twister. It has a better equidistribution property of v bit accuracy than MT but worse than WELL ("Well Equidistributed Long period Linear"). It has quicker recovery from zero excess initial state than MT, but slower than WELL. It supports various periods from 2607 − 1 to 2216091 − 1. Intel SSE2 and PowerPC AltiVec are supported by SFMT. It is also used for games with the Cell BE in the PlayStation 3. TinyMT is a variant of Mersenne Twister, proposed by Saito and Matsumoto in 2011. TinyMT uses just 127 bits of state space, a significant decrease compared to the original's 2.5 KiB of state. However, it has a period of , far shorter than the original, so it is only recommended by the authors in cases where memory is at a premium.
Альтернативы
Альтернативный генератор WELL ("Well Equidistributed Long period Linear") обеспечивает более быстрое восстановление, равнозначную случайность и почти такую же скорость. Генераторы xorshift Марсальи и их варианты – самые быстрые в классе LFSR. 64-битные MELG ("64-битные максимально равнораспределенные линейные генераторы с периодом, основанным на простом числе Мерсена") полностью оптимизированы с точки зрения свойств k-распределения. Семейство ACORN (опубликовано в 1989 году) – еще один k-распределенный PRNG, демонстрирующий схожую вычислительную скорость с MT и лучшие статистические характеристики, поскольку он соответствует всем современным (2019) критериям TestU01; при правильном выборе параметров ACORN может иметь произвольно большой период и точность. Семейство PCG – более современный генератор с длинным периодом, обладающий лучшей локальностью кэша и меньшей обнаруживаемой смещенностью при использовании современных методов анализа.