Русская Википедия:Xorshift

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Файл:Xorshift.png

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

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

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

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

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

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

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

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.