XorShift

XorShift — это класс генераторов псевдослучайных чисел (ГПСЧ), основанный на рекуррентном применении операции «исключающее ИЛИ» (XOR) и битовых сдвигов. Относится к семейству регистров сдвига с линейной обратной связью (LFSR), но отличается от классических LFSR тем, что использует нелинейную комбинацию сдвиговых операций, что позволяет достичь высокой скорости генерации и хороших статистических свойств при относительно малом объёме состояния. XorShift был предложен японским математиком и программистом Макото Мацумото (также известным как соавтор вихря Мерсенна) в 2003 году.

История

В 1990-е — начале 2000-х годов широкое распространение получили ГПСЧ на основе линейных конгруэнтных генераторов и вихря Мерсенна. Однако вихрь Мерсенна, несмотря на отличные статистические качества, требовал значительного объёма памяти (около 2,5 КБ) и не был оптимален для встраиваемых систем и приложений с жёсткими ограничениями по ресурсам. В 2003 году Макото Мацумото опубликовал статью «XorShift: A Fast, Portable, High-Quality Random Number Generator», в которой описал семейство генераторов, использующих исключительно операции XOR и битовые сдвиги. Основная цель заключалась в создании простого, быстрого и портативного ГПСЧ, который мог бы работать на любых процессорах с поддержкой 32- или 64-битной арифметики.

Первоначально XorShift не получил широкого распространения из-за выявленных статистических слабостей в некоторых вариантах, особенно в младших битах. Однако последующие модификации, такие как XorShift* (с умножением на константу) и XorShift+ (с добавлением), а также семейство xorshift1024, исправили эти недостатки. В 2014 году на основе XorShift был создан генератор Xoroshiro128 (xor/rotate/shift/rotate) и его вариант Xoroshiro128+, который стал одним из стандартных ГПСЧ в библиотеке Random123 и в языке программирования Julia. В 2016 году был предложен Xoshiro256 (xor/shift/rotate), который используется в качестве генератора по умолчанию в языке Lua (начиная с версии 5.4) и в некоторых реализациях стандартной библиотеки C++.

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

XorShift использует рекуррентное уравнение вида:

\[ x_{n+1} = x_n \oplus (x_n \ll a) \oplus (x_n \gg b) \oplus (x_n \ll c) \]

где \(x_n\) — текущее состояние (целое число), \(\oplus\) — операция XOR, \(\ll\) и \(\gg\) — битовые сдвиги влево и вправо, а \(a, b, c\) — целочисленные константы, определяющие конкретный вариант генератора. Состояние генератора обычно представляет собой одно или несколько машинных слов (32, 64 или 128 бит). После каждого вызова генератора состояние обновляется по указанной формуле, и из него извлекается выходное значение (часто — само состояние, либо его часть).

Пример 32-битного XorShift

Для 32-битного варианта с параметрами \(a=13, b=17, c=5\) алгоритм выглядит так:

1. \(t = x \oplus (x \ll 13)\)
2. \(t = t \oplus (t \gg 17)\)
3. \(x = t \oplus (t \ll 5)\)

Полученное значение \(x\) становится новым состоянием и одновременно выходным числом.

Пример 64-битного XorShift

Для 64-битного варианта часто используются параметры \(a=13, b=7, c=17\):

1. \(x = x \oplus (x \ll 13)\)
2. \(x = x \oplus (x \gg 7)\)
3. \(x = x \oplus (x \ll 17)\)

Классификация

По размеру состояния

• XorShift32 — состояние 32 бита, период \(2^{32} - 1\).
• XorShift64 — состояние 64 бита, период \(2^{64} - 1\).
• XorShift128 — состояние 128 бит (два 64-битных слова), период \(2^{128} - 1\).
• XorShift1024 — состояние 1024 бита (16 64-битных слов), период \(2^{1024} - 1\).

По модификациям

• XorShift — базовый вариант (чистый XorShift). Имеет проблемы с младшими битами.
• XorShift* — после сдвигов применяется умножение на нечётную константу (например, 0x2545F4914F6CDD1D для 64 бит). Улучшает равномерность распределения.
• XorShift+ — вместо умножения используется сложение двух частей состояния. Пример: Xoroshiro128+.
• Xoroshiro — вариант с вращением (rotate) вместо сдвига, что улучшает качество.
• Xoshiro — дальнейшее развитие с более сложной структурой (например, Xoshiro256**).

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

Скорость

XorShift-генераторы чрезвычайно быстры, так как используют только побитовые операции и сдвиги, которые выполняются процессором за один такт. На современных процессорах генерация одного случайного числа занимает 2–5 тактов, что значительно быстрее, чем вихрь Мерсенна (10–20 тактов) или криптостойкие ГПСЧ (сотни тактов).

Период

Период (длина последовательности до повторения) зависит от размера состояния:

• 32 бита: \(2^{32} - 1\) (около 4,3 миллиарда)
• 64 бита: \(2^{64} - 1\) (около \(1,8 \times 10^{19}\))
• 128 бит: \(2^{128} - 1\) (около \(3,4 \times 10^{38}\))
• 1024 бита: \(2^{1024} - 1\) (астрономическое число)

Для большинства практических приложений периода \(2^{128}\) более чем достаточно.

Статистическое качество

Базовые XorShift-генераторы проходят большинство стандартных тестов (например, тесты Diehard), но имеют слабые места, особенно в младших битах. Модификации XorShift* и XorShift+ исправляют эти недостатки и проходят более строгие тесты, такие как TestU01 (BigCrush). Однако XorShift-генераторы не являются криптостойкими — их последовательность можно восстановить по нескольким выходным значениям.

Потребление памяти

Требуют минимального объёма памяти: от 4 байт (32-битный) до 128 байт (1024-битный). Это делает их идеальными для встраиваемых систем, микроконтроллеров и GPU.

Применение

XorShift-генераторы широко используются в:

• Научных вычислениях — симуляции Монте-Карло, моделирование физических процессов, где требуется высокая скорость и хорошее качество.
• Компьютерной графике — генерация шума, процедурная текстура, трассировка лучей.
• Игровой индустрии — генерация игровых событий, процедурная генерация уровней.
• Криптографии — НЕ используются из-за предсказуемости, но могут применяться в некриптографических протоколах (например, для генерации nonce).
• Встроенных системах — благодаря малому потреблению памяти и быстродействию.
• Языках программирования — как генератор по умолчанию в Lua 5.4 (Xoshiro256**), Julia (Xoroshiro128+), а также в некоторых реализациях C++ (std::mt19937_64 остаётся вихрем Мерсенна, но XorShift используется в библиотеках Boost и Random123).

Примеры реализации

32-битный XorShift на C

```c

include <stdint.h>

static uint32_t x = 123456789; // начальное состояние

uint32_t xor32() { x ^= x << 13; x ^= x >> 17; x ^= x << 5; return x; } ```

64-битный XorShift* на C

```c

include <stdint.h>

static uint64_t state = 123456789; // начальное состояние

uint64_t xor64_star() { state ^= state << 13; state ^= state >> 7; state ^= state << 17; return state * 0x2545F4914F6CDD1D; } ```

Xoroshiro128+ на C

```c

include <stdint.h>

static uint64_t s[2] = {123456789, 987654321}; // начальное состояние

uint64_t xoroshiro128_plus() { uint64_t s0 = s[0]; uint64_t s1 = s[1]; uint64_t result = s0 + s1; s1 ^= s0; s[0] = ((s0 << 24) | (s0 >> 40)) ^ s1 ^ (s1 << 16); s[1] = (s1 << 37) | (s1 >> 27); return result; } ```

Критика

Основные недостатки XorShift:

• Неравномерность младших битов — в базовых вариантах младшие биты имеют меньший период и худшую случайность. Это исправляется в модификациях (XorShift*, XorShift+).
• Предсказуемость — как и любой не криптостойкий ГПСЧ, XorShift уязвим для атак по восстановлению состояния. Достаточно 2–3 выходных значений, чтобы восстановить всё состояние.
• Отсутствие гарантии качества — статистические свойства зависят от выбора параметров. Неправильный выбор констант может привести к очень короткому периоду или плохому распределению.
• Проблемы с параллелизмом — при использовании на GPU или в многопоточных приложениях требуется раздельное состояние для каждого потока, что может привести к корреляции между потоками.

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

• Название «XorShift» происходит от комбинации XOR (исключающее ИЛИ) и Shift (сдвиг).
• Макото Мацумото, создатель XorShift, является также соавтором вихря Мерсенна — одного из самых популярных ГПСЧ в мире.
• Xoroshiro128+ назван так из-за комбинации операций: XOR, rotate, shift, rotate.
• В 2018 году в языке Lua был проведён конкурс на замену старого ГПСЧ, и победителем стал Xoshiro256**.
• XorShift-генераторы используются в некоторых реализациях функции rand() в стандартной библиотеке C (например, в glibc до версии 2.36).

Источники

• Marsaglia, G. (2003). «XorShift: A Fast, Portable, High-Quality Random Number Generator». Journal of Statistical Software.
• Matsumoto, M., & Nishimura, T. (1998). «Mersenne Twister: A 623-dimensionally equidistributed uniform pseudo-random number generator». ACM Transactions on Modeling and Computer Simulation.
• Blackman, D., & Vigna, S. (2016). «Scrambled Linear Pseudorandom Number Generators». ACM Transactions on Mathematical Software.
• Vigna, S. (2017). «Further scramblings of Marsaglia's xorshift generators». Journal of Computational and Applied Mathematics.
• Документация к библиотеке Random123 (Lawrence Livermore National Laboratory).
• Стандарт языка Lua 5.4 — раздел «Random Number Generator».