Открыть сервис
Главная → Блог → Mersenne Twister

Mersenne Twister

Mersenne Twister (вихрь Мерсенна) — это генератор псевдослучайных чисел (ГПСЧ), разработанный в 1997 году японскими учёными Макото Мацумото и Такудзи Нисимурой. Относится к классу генераторов на основе регистров сдвига с линейной обратной связью. Основные характеристики: чрезвычайно длинный период (2^19937 − 1, что соответствует числу Мерсенна M19937), высокая скорость работы и хорошее статистическое качество выходной последовательности. Широко применяется в симуляциях, научных расчётах, компьютерной графике и криптографии (хотя не является криптостойким).

История

В 1990-х годах существовавшие ГПСЧ, такие как линейный конгруэнтный генератор (LCG) и регистры сдвига (например, Fibonacci LFSR), имели ограниченный период (обычно до 2^32) и проявляли статистические дефекты (корреляции между последовательными числами). Мацумото и Нисимура поставили цель создать генератор с периодом, близким к максимально возможному для 32-битных машин, и с равномерным распределением в 623 измерениях.

Алгоритм был опубликован в 1998 году в журнале ACM Transactions on Modeling and Computer Simulation. Название «Mersenne Twister» происходит от использования числа Мерсенна M19937 (2^19937 − 1) в качестве периода. Первоначальная реализация MT19937 (32-битная версия) быстро стала популярной благодаря включению в стандартные библиотеки языков программирования (C++, Python, R, MATLAB). В 2007 году вышла 64-битная версия MT19937-64, а в 2015 году — улучшенные варианты SFMT (SIMD-oriented Fast Mersenne Twister) и TinyMT.

Принцип работы

Основные компоненты

  • Состояние: массив из 624 32-битных слов (для MT19937) или 312 64-битных слов (для MT19937-64).
  • Индекс: указатель текущего слова в массиве (от 0 до 623).
  • Параметры: константы, определяющие рекуррентное соотношение (например, 397, 2567483615).

Алгоритм

  1. Инициализация: состояние заполняется начальным значением (seed) — обычно 32-битным числом. Для этого используется линейный конгруэнтный генератор с фиксированными параметрами.
  2. Генерация последовательности:
  • Для каждого слова из массива выполняется операция «скручивания» (twist):
  • Берётся текущее слово, слово с отступом 397 и слово с отступом 1.
  • Применяются битовые сдвиги, XOR и умножение на константу.
  • Результат записывается на место текущего слова.
  • После обработки всех 624 слов массив «скручивается» заново.
  1. Темперирование (tempering): к каждому сгенерированному слову применяется последовательность битовых операций (сдвиги, XOR, маски), чтобы улучшить статистическое распределение. Результат выдаётся как псевдослучайное число.

Период и равномерность

  • Период равен 2^19937 − 1, что является простым числом Мерсенна. Это означает, что последовательность не повторяется до исчерпания периода, что в 10^6000 раз больше, чем у типичных LCG.
  • Выходные числа равномерно распределены в 623-мерном пространстве (для 32-битной версии). Это свойство называется «623-мерная равномерность» и гарантирует отсутствие корреляций между группами из 623 последовательных чисел.

Разновидности

MT19937 (32-битная)

  • Базовая версия с периодом 2^19937 − 1.
  • Размер состояния: 624 слова (2,5 КБ).
  • Скорость: ~100–200 млн чисел в секунду на современных процессорах.

MT19937-64 (64-битная)

  • Аналогична MT19937, но использует 64-битные слова.
  • Размер состояния: 312 слов (2,5 КБ).
  • Период тот же, но выходные числа — 64-битные.

SFMT (SIMD-oriented Fast Mersenne Twister)

  • Оптимизированная версия, использующая SIMD-инструкции (SSE2, AVX) для параллельной обработки.
  • В 2–4 раза быстрее MT19937.
  • Период может варьироваться (2^19937 − 1, 2^4253 − 1 и др.).

TinyMT

  • Компактная версия с малым состоянием (127 бит) и периодом 2^127 − 1.
  • Предназначена для встраиваемых систем и мобильных устройств.

Применение

Научные расчёты

Компьютерная графика

  • Генерация текстур, шумов (Perlin noise, симуляция облаков).
  • Рендеринг (сглаживание, распределение лучей).
  • Анимация частиц и физических эффектов.

Игровая индустрия

  • Генерация случайных событий (выпадение предметов, поведение ИИ).
  • Процедурная генерация уровней и карт.

Криптография (ограниченно)

  • Не является криптостойким: по состоянию можно восстановить все предыдущие и последующие числа (атака по восстановлению состояния). Не рекомендуется для шифрования, генерации ключей или токенов.
  • Используется в некоторых криптосистемах как вспомогательный ГПСЧ (например, в OpenSSL до версии 1.1.1 — для генерации случайных чисел в тестах).

Достоинства и недостатки

Достоинства

  • Огромный период (2^19937 − 1).
  • Высокая скорость (в 2–5 раз быстрее LCG с аналогичным качеством).
  • Хорошее статистическое качество (проходит большинство тестов Diehard, TestU01, NIST).
  • Простая реализация и малый размер состояния.

Недостатки

  • Не криптостойкий: при известном состоянии можно восстановить всю последовательность. Для криптографии следует использовать CSPRNG (например, ChaCha20, AES-CTR).
  • Зависимость от начального значения: при одинаковом seed генерируется идентичная последовательность (что может быть как плюсом для воспроизводимости, так и минусом для безопасности).
  • Память: состояние 2,5 КБ может быть избыточным для встраиваемых систем.
  • Периодические корреляции: при выборке чисел с шагом, кратным 624, могут проявляться корреляции (хотя на практике это редко).

Критика и альтернативы

В 2010-х годах были выявлены некоторые недостатки Mersenne Twister:

  • Большое состояние затрудняет использование в устройствах с ограниченной памятью.
  • Неустойчивость к «застреванию»: при неправильной инициализации (например, seed = 0) может генерировать последовательность с нулевыми значениями.
  • Уязвимость к атакам по времени: для криптографических приложений не подходит.

В ответ были разработаны альтернативы:

  • PCG (Permuted Congruential Generator) — быстрее и компактнее (64 бита состояния), проходит тесты Dieharder.
  • Xorshift (Джордж Марсалья) — очень быстрый, но с меньшим периодом (2^128 − 1).
  • ChaCha20 — криптостойкий ГПСЧ, используемый в Linux /dev/urandom и OpenBSD.

Тем не менее, Mersenne Twister остаётся стандартом для не-криптографических приложений благодаря балансу скорости, качества и простоты.

Интересные факты

  • Период MT19937 (2^19937 − 1) настолько велик, что для его исчерпания при скорости генерации 1 млрд чисел в секунду потребуется более 10^6000 лет.
  • Алгоритм назван в честь французского математика Марена Мерсенна (1588–1648), изучавшего числа вида 2^n − 1.
  • Mersenne Twister включён в стандартную библиотеку C++ (std::mt19937), Python (random.getrandbits), R (set.seed), MATLAB (rng) и многих других языков.
  • В 2015 году Мацумото и Нисимура выпустили версию SFMT с поддержкой SIMD, которая в 4 раза быстрее оригинальной.

Источники

  • Matsumoto, M., & Nishimura, T. (1998). «Mersenne Twister: A 623-dimensionally equidistributed uniform pseudo-random number generator». ACM Transactions on Modeling and Computer Simulation, 8(1), 3–30.
  • Matsumoto, M., & Nishimura, T. (2000). «Dynamic Creation of Pseudorandom Number Generators». Monte Carlo and Quasi-Monte Carlo Methods 1998, 56–69.
  • Saito, M., & Matsumoto, M. (2008). «SIMD-oriented Fast Mersenne Twister: a 128-bit pseudorandom number generator». Monte Carlo and Quasi-Monte Carlo Methods 2006, 607–622.
  • L'Ecuyer, P. (2012). «Random Number Generation». Handbook of Computational Statistics, 35–71.
  • Knuth, D. E. (1997). «The Art of Computer Programming, Volume 2: Seminumerical Algorithms» (3rd ed.). Addison-Wesley.

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →

Похожие материалы