Xorshift

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

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

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

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

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

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

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

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.

Примечания
  1. Marsaglia, George (July 2003). “Xorshift RNGs”. Journal of Statistical Software. 8 (14). DOI:10.18637/jss.v008.i14.
  2. Brent, Richard P. (August 2004). “Note on Marsaglia's Xorshift Random Number Generators”. Journal of Statistical Software. 11 (5). DOI:10.18637/jss.v011.i05.
  3. Panneton, François; L'Ecuyer, Pierre (October 2005). “On the xorshift random number generators” (PDF). ACM Transactions on Modeling and Computer Simulation. 15 (4): 346—361. DOI:10.1145/1113316.1113319. Неизвестный параметр |s2cid= (справка)
  4. Vigna, Sebastiano xorshift*/xorshift+ generators and the PRNG shootout. Дата обращения: 25 октября 2014.
  5. Lemire, Daniel; O’Neill, Melissa E. (April 2019). “Xorshift1024*, Xorshift1024+, Xorshift128+ and Xoroshiro128+ Fail Statistical Tests for Linearity”. Computational and Applied Mathematics. 350: 139—142. arXiv:1810.05313. DOI:10.1016/j.cam.2018.10.019. We report that these scrambled generators systematically fail Big Crush—specifically the linear-complexity and matrix-rank tests that detect linearity—when taking the 32 lowest-order bits in reverse order from each 64-bit word. Неизвестный параметр |s2cid= (справка)
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.