Xorshift

Пример случайного распределения Xorshift128

Xorshift (также «генераторы регистров сдвига») — класс генераторов псевдослучайных чисел, открытых Джорджем Марсалья. Генераторы такого типа представляют собой подмножество регистров сдвига с линейной обратной связью (LFSR), что позволяет эффективно реализовать их без чрезмерного использования разреженных многочленов. Генерация следующего числа в последовательности происходит путём многократного вычисления исключающее «ИЛИ» текущего числа и его битового сдвига, что делает xorshift чрезвычайно быстрыми на современных компьютерных архитектурах. Как и все LFSR, xorshift требуют тщательного подбора начальных параметров, для получения более длинных периодических последовательностей.

Генераторы Xorshift являются одними из самых быстрых криптографически нестойких генераторов случайных чисел, а их реализация не предполагает больших объёмов кода или сохраняемого состояния системы. Хотя «в сыром виде» они не проходят все статистические тесты случайности, этот недочёт хорошо известен и легко исправляется путём добавления в их структуру нелинейной функции, в результате чего получаются такие генераторы как xorshift+ или xorshift*. Реализация генератора xorshift+ на языке C, которая проходит все тесты из набора BigCrush (с на порядок меньшим числом неудач, чем вихрь Мерсенна или WELL), обычно требует менее 10 тактов на x86 для генерации случайного числа благодаря конвейерной обработке команд.

Скремблеры, известные как + и *, слабы в младших битах и предназначены для генерации чисел с плавающей запятой, поскольку преобразование случайного числа в вещественное отбрасывает младшие биты. В общем случае скремблер ** (произносится как «starstar») позволяет LFSR проходить тесты на всех битах.

Поскольку простые генераторы xorshift (без нелинейного этапа) не проходят несколько статистических тестов, они считаются ненадёжными.

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

Ниже приведена реализация 128-битной версии xorshift на C. Приведённая реализация хранит четыре 32-битных числа в качестве состояния и имеет период, равный $2^{128}-1$.

struct xorshift128_state {
  uint32_t a, b, c, d;
};

/* The state array must be initialized to not be all zero */
uint32_t xorshift128(struct xorshift128_state *state)
{
	/* Algorithm "xor128" from p. 5 of Marsaglia, "Xorshift RNGs" */
	uint32_t t = state->d;

	uint32_t const s = state->a;
	state->d = state->c;
	state->c = state->b;
	state->b = s;

	t ^= t << 11;
	t ^= t >> 8;
	return state->a = t ^ s ^ (s >> 19);
}

Данная реализация проходит тесты diehard, однако не проходит тесты MatrixRank и LinearComp из тестового набора BigCrush пакета TestU01.