Открыть сервис
Главная → Блог → Вихрь Мерсенна

Вихрь Мерсенна

Вихрь Мерсенна (англ. Mersenne Twister) — это генератор псевдослучайных чисел (ГПСЧ), разработанный в 1997 году японскими учёными Макото Мацумото и Такудзи Нисимурой. Он основан на рекурсии в конечном поле GF(2) и известен своим чрезвычайно длинным периодом (2¹⁹⁹³⁷ − 1), что и отражено в названии (число Мерсенна M₁₉₉₃₇). Вихрь Мерсенна является одним из наиболее широко используемых ГПСЧ в научных вычислениях, симуляциях и компьютерных играх благодаря сочетанию высокой скорости работы, хороших статистических свойств и простоты реализации.

История

Разработка Вихря Мерсенна была мотивирована недостатками существовавших на тот момент генераторов псевдослучайных чисел. Линейные конгруэнтные генераторы (LCG), широко применявшиеся в 1980-е и 1990-е годы, имели короткий период (обычно 2³² или 2⁶⁴) и страдали от корреляций между последовательными значениями, что делало их непригодными для сложных симуляций. Генераторы на основе регистров сдвига с линейной обратной связью (LFSR) были быстрее, но также имели ограниченный период и статистические дефекты.

Мацумото и Нисимура представили свою работу «Mersenne Twister: A 623-dimensionally equidistributed uniform pseudo-random number generator» на конференции ACM в 1998 году. В статье они описали алгоритм, который обеспечивал период 2¹⁹⁹³⁷ − 1 и равномерное распределение в 623 измерениях (для 32-битных выходных значений). Это было значительным улучшением по сравнению с предшественниками. Первоначальная реализация, известная как MT19937, стала стандартом де-факто для многих приложений.

В 2002 году Мацумото и Нисимура совместно с Сайто (Saito) представили улучшенную версию — SFMT (SIMD-oriented Fast Mersenne Twister), оптимизированную для использования SIMD-инструкций процессоров (SSE2, AltiVec). В 2007 году была опубликована версия TinyMT, предназначенная для встраиваемых систем с ограниченными ресурсами. В 2015 году вышла версия MT19937-64, генерирующая 64-битные числа.

Алгоритм

Вихрь Мерсенна является частным случаем обобщённого регистра сдвига с линейной обратной связью (GFSR). Его работа основана на рекурсии в поле GF(2), где все операции выполняются над битами.

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

  1. Состояние (state): Массив из n 32-битных (или 64-битных) беззнаковых целых чисел. Для стандартного MT19937 n = 624. Это состояние полностью определяет текущую позицию генератора.
  2. Индекс (index): Указатель на текущий элемент в массиве состояния. Изначально равен n (что сигнализирует о необходимости начальной генерации).
  3. Параметры рекурсии: Набор констант, определяющих поведение алгоритма. Для MT19937:
  • w — разрядность слова (32 бита)
  • n — степень рекурсии (624)
  • m — средний член (397)
  • r — точка разделения слова (31)
  • a — коэффициенты матрицы скручивания (0x9908B0DF)
  • u, d, s, b, t, c, l — параметры для финальной обработки (темперирования)
  • f — множитель инициализации (1812433253)

Этапы работы

  1. Инициализация:
  • Заполняется начальное состояние массива на основе seed-значения (ключа). Обычно используется простая линейная рекурсия: state[0] = seed, state[i] = f * (state[i-1] XOR (state[i-1] >> (w-2))) + i.
  • Индекс устанавливается в n.
  1. Генерация (скручивание):
  • Когда индекс достигает n, выполняется процедура скручивания (twist). Для каждого i от 0 до n-1:
  • x = (state[i] & upper_mask) | (state[(i+1) % n] & lower_mask), где upper_mask — старшие w-r бит, lower_mask — младшие r бит.
  • x >>= 1
  • Если младший бит x был равен 1, то x ^= a.
  • state[i] = state[(i + m) % n] ^ x.
  • После скручивания индекс сбрасывается в 0.
  1. Темперирование:
  • Извлекается текущее значение state[index].
  • Применяется последовательность битовых операций (XOR, сдвиги, умножения) для улучшения равномерности распределения:
  • y = state[index]
  • y ^= (y >> u) & d
  • y ^= (y << s) & b
  • y ^= (y << t) & c
  • y ^= (y >> l)
  • Индекс увеличивается на 1.
  • Возвращается y как следующее псевдослучайное число.

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

Период

Период Вихря Мерсенна составляет 2¹⁹⁹³⁷ − 1, что является простым числом Мерсенна. Это означает, что последовательность не повторяется в течение примерно 10⁶⁰⁰⁰ шагов, что более чем достаточно для подавляющего большинства практических приложений.

Равномерность

Алгоритм обеспечивает k-распределённость (k-distribution) для всех k до 623 (для 32-битных выходов). Это означает, что последовательность из k последовательных 32-битных чисел равномерно распределена в 623-мерном пространстве. Это свойство существенно превосходит возможности LCG и LFSR.

Скорость

Вихрь Мерсенна является одним из самых быстрых ГПСЧ с длинным периодом. Скручивание выполняется один раз на каждые 624 вызова, а темперирование — это всего несколько битовых операций. На современных процессорах он генерирует миллионы случайных чисел в секунду.

Недостатки

  1. Большое состояние: Требуется 2.5 КБ памяти (624 × 4 байта) для состояния, что может быть проблемой для встраиваемых систем.
  2. Медленная инициализация: Заполнение начального состояния требует времени, особенно при большом seed.
  3. Предсказуемость: Как и любой детерминированный ГПСЧ, Вихрь Мерсенна не подходит для криптографических целей. Зная 624 последовательных 32-битных числа, можно восстановить всё состояние генератора и предсказать все будущие значения.
  4. Корреляции в высоких измерениях: Хотя алгоритм имеет хорошую k-распределённость, в некоторых тестах (например, TestU01) были обнаружены слабые корреляции в многомерных пространствах, особенно для версии MT19937.
  5. Отсутствие криптостойкости: Вихрь Мерсенна не является криптографически стойким генератором. Его выходные данные можно легко отличить от истинно случайных с помощью статистических тестов, а также восстановить состояние.

Применение

Вихрь Мерсенна широко используется в областях, где требуется качественная псевдослучайность, но не требуется криптостойкость:

  • Научные вычисления: Моделирование методом Монте-Карло, симуляции физических процессов, статистические расчёты.
  • Компьютерные игры: Генерация случайных событий, процедурная генерация контента, искусственный интеллект.
  • Программное обеспечение: Языки программирования (Python, Ruby, PHP, R, C++ в некоторых реализациях) используют Вихрь Мерсенна как стандартный ГПСЧ.
  • Численные методы: Генерация случайных чисел для интегралов, оптимизации, стохастических алгоритмов.
  • Тестирование: Генерация тестовых данных для программного обеспечения.

Варианты и модификации

  • MT19937: Стандартная 32-битная версия с периодом 2¹⁹⁹³⁷ − 1.
  • MT19937-64: 64-битная версия с тем же периодом, но с 64-битными словами.
  • SFMT (SIMD-oriented Fast Mersenne Twister): Оптимизированная версия для SIMD-инструкций, обеспечивающая более высокую скорость.
  • TinyMT: Уменьшенная версия для встраиваемых систем с периодом 2¹²⁷ − 1 и состоянием 128 бит.
  • MTGP (Mersenne Twister for Graphic Processors): Версия, адаптированная для GPU.
  • dSFMT (Double-precision SIMD-oriented Fast Mersenne Twister): Версия, генерирующая числа с плавающей точкой двойной точности.

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

Несмотря на широкое распространение, Вихрь Мерсенна подвергается критике за несоответствие современным требованиям к ГПСЧ. Основные претензии:

  • Недостаточная статистическая надёжность: В тестах TestU01 (BigCrush) MT19937 не проходит некоторые тесты, особенно в многомерных пространствах.
  • Большое состояние: Для многих приложений (например, встраиваемые системы) 2.5 КБ состояния — это много.
  • Сложность восстановления состояния: Хотя это и недостаток для криптографии, для научных вычислений это может быть проблемой при отладке.

В качестве альтернатив предлагаются:

  • Xorshift: Семейство генераторов с очень маленьким состоянием и высокой скоростью.
  • PCG (Permuted Congruential Generator): Сочетает простоту LCG с улучшенными статистическими свойствами.
  • WELL (Well Equidistributed Long-period Linear): Разработан для устранения недостатков Вихря Мерсенна.
  • ChaCha и другие криптографические ГПСЧ: Обеспечивают криптостойкость, но медленнее.

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

  • Название «Вихрь Мерсенна» происходит от периода 2¹⁹⁹³⁷ − 1, который является числом Мерсенна (простым числом вида 2ᵖ − 1). Сам алгоритм не имеет прямого отношения к вихрям или Мерсенну.
  • В 2019 году исследователи из Университета Цукубы (Япония) обнаружили, что в некоторых реализациях MT19937 существует слабая корреляция между последовательными числами, что может влиять на результаты симуляций.
  • Вихрь Мерсенна является генератором по умолчанию в Python (модуль random), Ruby, PHP, R и многих других языках программирования.

Источники

  • 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.
  • 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., & Simard, R. (2007). TestU01: A C library for empirical testing of random number generators. ACM Transactions on Mathematical Software, 33(4), 22.
  • Knuth, D. E. (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd ed.). Addison-Wesley.

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

На главную BFOmetr →

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