✖


Jump to content

Ксоршифт

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

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

Для выполнения в программном обеспечении генераторы xorshift являются одними из самых быстрых ГПСЧ, требующих очень небольшого кода и состояния. Однако они не проходят все статистические тесты без дальнейшей доработки. Этот недостаток устраняется путем объединения их с нелинейной функцией, как описано в оригинальной статье. Поскольку простые генераторы xorshift (без нелинейного шага) не проходят некоторые статистические тесты, их обвиняют в ненадежности. [3] : 360 

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

[ редактировать ]

C ​ Версия [а] из трех алгоритмов xorshift [1] : 4,5  дано здесь. Первый имеет одно 32-битное слово состояния и период 2. 32 −1. Второй имеет одно 64-битное слово состояния и период 2. 64 −1. Последний имеет четыре 32-битных слова состояния и период 2. 128 −1. 128-битный алгоритм выдерживает жесткие испытания . Однако он не проходит MatrixRank и LinearComp тесты набора тестов BigCrush из платформы TestU01 .

Все они используют три смены и три или четыре операции «исключающее ИЛИ»: 

#include <stdint.h>

struct xorshift32_state {
    uint32_t a;
};

/* The state must be initialized to non-zero */
uint32_t xorshift32(struct xorshift32_state *state)
{
	/* Algorithm "xor" from p. 4 of Marsaglia, "Xorshift RNGs" */
	uint32_t x = state->a;
	x ^= x << 13;
	x ^= x >> 17;
	x ^= x << 5;
	return state->a = x;
}

struct xorshift64_state {
    uint64_t a;
};

uint64_t xorshift64(struct xorshift64_state *state)
{
	uint64_t x = state->a;
	x ^= x << 13;
	x ^= x >> 7;
	x ^= x << 17;
	return state->a = x;
}

/* struct xorshift128_state can alternatively be defined as a pair
   of uint64_t or a uint128_t where supported */
struct xorshift128_state {
    uint32_t x[4];
};

/* The state must be initialized to non-zero */
uint32_t xorshift128(struct xorshift128_state *state)
{
	/* Algorithm "xor128" from p. 5 of Marsaglia, "Xorshift RNGs" */
	uint32_t t  = state->x[3];
    
    uint32_t s  = state->x[0];  /* Perform a contrived 32-bit shift. */
	state->x[3] = state->x[2];
	state->x[2] = state->x[1];
	state->x[1] = s;

	t ^= t << 11;
	t ^= t >> 8;
	return state->x[0] = t ^ s ^ (s >> 19);
}

В случае одного 64-битного слова состояния существуют параметры, которые содержат период 2. 64 −1 с двумя парами «исключающее ИЛИ» и сдвиг. [4] 

#include <stdint.h>

struct xorshift64_state {
  uint64_t a;
};

uint64_t xorshift64(struct xorshift64_state *state)
{
	uint64_t x = state->a;
	x ^= x << 7;
	x ^= x >> 9;
	return state->a = x;
}

Нелинейные вариации

[ редактировать ]

Все генераторы xorshift не проходят некоторые тесты в наборе тестов BigCrush . Это справедливо для всех генераторов, основанных на линейных рекуррентах, таких как Mersenne Twister или WELL . Однако выходные данные таких генераторов легко зашифровать, чтобы улучшить их качество.

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

бесплатно

[ редактировать ]

Марсалья предложил зашифровать выходной сигнал, объединив его с простым аддитивным счетчиком по модулю 2. 32 (которую он называет « последовательностью Вейля » в честь теоремы Вейля о равнораспределении ). Это также увеличивает период в 2 раза. 32 , до 2 192 −2 32 : 

#include <stdint.h>

struct xorwow_state {
    uint32_t x[5];
    uint32_t counter;
};

/* The state array must be initialized to not be all zero in the first four words */
uint32_t xorwow(struct xorwow_state *state)
{
    /* Algorithm "xorwow" from p. 5 of Marsaglia, "Xorshift RNGs" */
    uint32_t t  = state->x[4];
 
    uint32_t s  = state->x[0];  /* Perform a contrived 32-bit shift. */
    state->x[4] = state->x[3];
    state->x[3] = state->x[2];
    state->x[2] = state->x[1];
    state->x[1] = s;
 
    t ^= t >> 2;
    t ^= t << 1;
    t ^= s ^ (s << 4);
    state->x[0] = t;
    state->counter += 362437;
    return t + state->counter;
}

Он работает хорошо, но не проходит несколько тестов в BigCrush. [7] Этот генератор используется по умолчанию в наборе инструментов CUDA от Nvidia . [8]

xorshift*

[ редактировать ]

Генератор xorshift* применяет обратимое умножение (по модулю размера слова) в качестве нелинейного преобразования к выходным данным генератора xorshift , как предложил Марсалья. [1] Все генераторы xorshift* выдают последовательность значений, равномерно распределенную в максимально возможном измерении (за исключением того, что они никогда не выдают ноль при 16 вызовах, т.е. 128 байтах подряд). [9]

Следующий 64-битный генератор имеет максимальный период 2 64 −1. [9] 

#include <stdint.h>

/* xorshift64s, variant A_1(12,25,27) with multiplier M_32 from line 3 of table 5 */
uint64_t xorshift64star(void) {
    /* initial seed must be nonzero, don't use a static variable for the state if multithreaded */
    static uint64_t x = 1;
    x ^= x >> 12;
    x ^= x << 25;
    x ^= x >> 27;
    return x * 0x2545F4914F6CDD1DULL;
}

Генератор не проходит только тест MatrixRank BigCrush, однако, если генератор модифицирован так, чтобы возвращать только старшие 32 бита, то он проходит BigCrush без ошибок. [10] : 7  Фактически, сокращенная версия, имеющая всего 40 бит внутреннего состояния, проходит этот набор, что предполагает большой запас прочности. [10] : 19  Похожий генератор предложен в «Численных рецептах». [11] как RanQ1 также не проходит тест BirthdaySpacings .

Винья [9] предлагает следующий генератор xorshift1024* с 1024 битами состояния и максимальным периодом 2 1024 −1; однако он не всегда проходит BigCrush. [5] Поэтому xoshiro256** — гораздо лучший вариант. 

#include <stdint.h>

/* The state must be seeded so that there is at least one non-zero element in array */
struct xorshift1024s_state {
	uint64_t x[16];
	int index;
};

uint64_t xorshift1024s(struct xorshift1024s_state *state)
{
	int index = state->index;
	uint64_t const s = state->x[index++];
	uint64_t t = state->x[index &= 15];
	t ^= t << 31;		// a
	t ^= t >> 11;		// b  -- Again, the shifts and the multipliers are tunable
	t ^= s ^ (s >> 30);	// c
	state->x[index] = t;
	state->index = index;
	return t * 1181783497276652981ULL;
}

xorshift+

[ редактировать ]

Генератор xorshift+ может добиться на порядок меньше отказов, чем Mersenne Twister или WELL . Собственная реализация генератора xorshift+ на языке C, которая проходит все тесты из пакета BigCrush, обычно может генерировать случайное число менее чем за 10 тактов на x86 благодаря конвейерной обработке инструкций . [12]

Вместо умножения можно использовать сложение как более быстрое нелинейное преобразование. Идея была впервые предложена Сайто и Мацумото (также ответственными за Mersenne Twister) в генераторе XSadd , который добавляет два последовательных вывода базового генератора xorshift на основе 32-битных сдвигов. [13] Однако один из недостатков добавления последовательных выходных данных заключается в том, что, хотя базовый генератор xorshift128 является равнораспределенным в двух измерениях, генератор xorshift128+ распределяется только в одном измерении. [14]

XSadd имеет некоторые недостатки в младших битах вывода; он проваливает несколько тестов BigCrush, когда выходные слова инвертируются. Чтобы исправить эту проблему, Vigna представила семейство xorshift+ , [14] на основе 64-битных сдвигов. Генераторы xorshift+ , даже такие большие, как xorshift1024+ , демонстрируют некоторую заметную линейность в младших битах своего вывода; [5] он проходит BigCrush, но не проходит, когда 32 младших бита используются в обратном порядке от каждого 64-битного слова. [5] Этот генератор является одним из самых быстрых генераторов, проходящих BigCrush. [12]

Следующий генератор xorshift128+ использует 128 бит состояния и имеет максимальный период 2. 128 −1. 

#include <stdint.h>

struct xorshift128p_state {
    uint64_t x[2];
};

/* The state must be seeded so that it is not all zero */
uint64_t xorshift128p(struct xorshift128p_state *state)
{
	uint64_t t = state->x[0];
	uint64_t const s = state->x[1];
	state->x[0] = s;
	t ^= t << 23;		// a
	t ^= t >> 18;		// b -- Again, the shifts and the multipliers are tunable
	t ^= s ^ (s >> 5);	// c
	state->x[1] = t;
	return t + s;
}

Хосиро

[ редактировать ]

xoshiro (сокращение от «xor, сдвиг, поворот») и xoroshiro (сокращение от «xor, Rotate, сдвиг, поворот») используют вращение в дополнение к сдвигам. По словам Винья, они быстрее и производят более качественный результат, чем xorshift. [15] [16]

Этот класс генераторов имеет варианты для вывода 32-битных и 64-битных целых чисел и чисел с плавающей запятой; для плавающей запятой берутся старшие 53 бита (для бинарного64 ) или старшие 23 бита (для бинарного32 ), поскольку старшие биты имеют лучшее качество, чем младшие биты в генераторах с плавающей запятой. Алгоритмы также включают в себя jump функция, которая устанавливает состояние вперед на некоторое количество шагов — обычно степень двойки, которая позволяет многим потокам выполнения запускаться в разных начальных состояниях.

Для 32-битного вывода xoshiro128** и xoshiro128+ в точности эквивалентны xoshiro256** и xoshiro256+, причем uint32_t вместо uint64_t и с разными константами сдвига/поворота.

Совсем недавно, Генераторы xoshiro++ были созданы как альтернатива генераторам xoshiro++. xoshiro** генераторы . Они используются в некоторых реализациях компиляторов Фортрана , таких как GNU Fortran, Java и Julia . [17]

xoshiro256**

[ редактировать ]

xoshiro256** — универсальный генератор случайных 64-битных чисел. Он используется в GNU Fortran компиляторе , Lua (начиная с Lua 5.4) и .NET framework (начиная с .NET 6.0). [17] 

/*  Adapted from the code included on Sebastiano Vigna's website */

#include <stdint.h>

uint64_t rol64(uint64_t x, int k)
{
	return (x << k) | (x >> (64 - k));
}

struct xoshiro256ss_state {
	uint64_t s[4];
};

uint64_t xoshiro256ss(struct xoshiro256ss_state *state)
{
	uint64_t *s = state->s;
	uint64_t const result = rol64(s[1] * 5, 7) * 9;
	uint64_t const t = s[1] << 17;

	s[2] ^= s[0];
	s[3] ^= s[1];
	s[1] ^= s[2];
	s[0] ^= s[3];

	s[2] ^= t;
	s[3] = rol64(s[3], 45);

	return result;
}

xoshiro256+

[ редактировать ]

xoshiro256+ примерно на 15 % быстрее, чем xoshiro256**, но три младших бита имеют низкую линейную сложность; поэтому его следует использовать только для результатов с плавающей запятой путем извлечения старших 53 битов. 

#include <stdint.h>

uint64_t rol64(uint64_t x, int k)
{
	return (x << k) | (x >> (64 - k));
}

struct xoshiro256p_state {
	uint64_t s[4];
};

uint64_t xoshiro256p(struct xoshiro256p_state *state)
{
	uint64_t* s = state->s;
	uint64_t const result = s[0] + s[3];
	uint64_t const t = s[1] << 17;

	s[2] ^= s[0];
	s[3] ^= s[1];
	s[1] ^= s[2];
	s[0] ^= s[3];

	s[2] ^= t;
	s[3] = rol64(s[3], 45);

	return result;
}

Хороширо

[ редактировать ]

Если пространство ограничено, xoroshiro128** и xoroshiro128+ эквивалентны xoshiro256** и xoshiro256+. Они имеют меньшее пространство состояний и поэтому менее полезны для программ с массовым параллелизмом. xoroshiro128+ также демонстрирует умеренную зависимость в количестве населения , вызывая сбой после 5 ТБ вывода . Авторы не верят, что это можно обнаружить в реальных программах.

xoroshiro64** и xoroshiro64* эквивалентны xoroshiro128** и xoroshiro128+. В отличие от генераторов xoshiro, они не являются простыми портами своих высокоточных аналогов.

Инициализация

[ редактировать ]

В статье xoshiro рекомендуется инициализировать состояние генераторов, используя генератор, который радикально отличается от инициализированных генераторов, а также тот, который никогда не будет давать «все нулевое» состояние; для генераторов сдвиговых регистров из этого состояния невозможно выйти. [16] [18] Авторы особенно рекомендуют использовать генератор SplitMix64 из 64-битного начального числа следующим образом: 

#include <stdint.h>

struct splitmix64_state {
	uint64_t s;
};

uint64_t splitmix64(struct splitmix64_state *state) {
	uint64_t result = (state->s += 0x9E3779B97f4A7C15);
	result = (result ^ (result >> 30)) * 0xBF58476D1CE4E5B9;
	result = (result ^ (result >> 27)) * 0x94D049BB133111EB;
	return result ^ (result >> 31);
}

struct xorshift128_state {
    uint32_t x[4];
};

// one could do the same for any of the other generators
void xorshift128_init(struct xorshift128_state *state, uint64_t seed) {
	struct splitmix64_state smstate = {seed};

	uint64_t tmp = splitmix64(&smstate);
	state->x[0] = (uint32_t)tmp;
	state->x[1] = (uint32_t)(tmp >> 32);

	tmp = splitmix64(&smstate);
	state->x[2] = (uint32_t)tmp;
	state->x[3] = (uint32_t)(tmp >> 32);
}

Примечания

[ редактировать ]
  1. ^ В C и большинстве других языков на основе C, ^ представляет побитовое исключающее ИЛИ и << и >> представляют собой побитовые сдвиги .

Ссылки

[ редактировать ]
  1. ^ Перейти обратно: а б с Марсалья, Джордж (июль 2003 г.). «Xorshift RNG» . Журнал статистического программного обеспечения . 8 (14). дои : 10.18637/jss.v008.i14 .
  2. ^ Брент, Ричард П. (август 2004 г.). «Заметка о генераторах случайных чисел Xorshift Марсальи» . Журнал статистического программного обеспечения . 11 (5). дои : 10.18637/jss.v011.i05 . hdl : 1885/34049 .
  3. ^ Перейти обратно: а б Паннетон, Франсуа; Л'Экуйер, Пьер (октябрь 2005 г.). «О генераторах случайных чисел xorshift» (PDF) . ACM-транзакции по моделированию и компьютерному моделированию . 15 (4): 346–361. дои : 10.1145/1113316.1113319 . S2CID   11136098 .
  4. ^ Исаку Вада «Хорошие случайные числа и плохие случайные числа» Проверено 28 августа 2023 г. Параметры : только (7,9) и (9.7).
  5. ^ Перейти обратно: а б с д Лемир, Дэниел; О'Нил, Мелисса Э. (апрель 2019 г.). «Xorshift1024*, Xorshift1024+, Xorshift128+ и Xoroshiro128+ не прошли статистические тесты на линейность». Вычислительная и прикладная математика . 350 : 139–142. arXiv : 1810.05313 . дои : 10.1016/j.cam.2018.10.019 . S2CID   52983294 . Мы сообщаем, что эти скремблированные генераторы систематически не проходят Big Crush — в частности, тесты линейной сложности и матричного ранга, которые обнаруживают линейность — при взятии 32 младших битов в обратном порядке из каждого 64-битного слова.
  6. ^ «ИСО/МЭК 60559:2020» . ИСО .
  7. ^ Ле Флок, Фабьен (12 января 2011 г.). «Результаты XORWOW L'ecuyer TestU01» . В погоне за дьяволом (блог) . Проверено 2 ноября 2017 г.
  8. ^ «Тестирование cuRAND» . Нвидиа . Проверено 2 ноября 2017 г.
  9. ^ Перейти обратно: а б с Винья, Себастьяно (июль 2016 г.). «Экспериментальное исследование зашифрованных генераторов xorshift Марсальи» (PDF) . Транзакции ACM в математическом программном обеспечении . 42 (4): 30. arXiv : 1402.6246 . дои : 10.1145/2845077 . S2CID   13936073 . Предлагает генераторы xorshift*, добавляющие итоговое умножение на константу.
  10. ^ Перейти обратно: а б О'Нил, Мелисса Э. (5 сентября 2014 г.). PCG: семейство простых быстрых и статистически эффективных алгоритмов генерации случайных чисел (PDF) (технический отчет). Колледж Харви Мадда . стр. 6–8. HMC-CS-2014-0905.
  11. ^ Пресс, WH ; Теукольский, С.А. ; Феттерлинг, WT; Фланнери, BP (2007). «Раздел 7.1.2.A. 64-битный метод Xorshift» . Численные рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN  978-0-521-88068-8 .
  12. ^ Перейти обратно: а б Винья, Себастьяно. «Генераторы xorshift*/xorshift+ и перестрелка PRNG» . Проверено 25 октября 2014 г.
  13. ^ Сайто, Муцуо; Мацумото, Макото (2014). «XORSHIFT-ADD (XSadd): вариант XORSHIFT» . Проверено 25 октября 2014 г.
  14. ^ Перейти обратно: а б Винья, Себастьяно (май 2017 г.). «Дальнейшие усовершенствования генераторов xorshift Марсальи» (PDF) . Журнал вычислительной и прикладной математики . 315 (С): 175–181. arXiv : 1404.0390 . дои : 10.1016/j.cam.2016.11.006 . S2CID   6876444 . Описывает генераторы xorshift+, обобщение XSadd.
  15. ^ Винья, Себастьяно. «Генераторы xoshiro/xoroshiro и перестрелка PRNG» . Проверено 7 июля 2019 г.
  16. ^ Перейти обратно: а б Блэкман, Дэвид; Винья, Себастьяно (2018). «Генератор зашифрованных линейных псевдослучайных чисел». Структуры данных и алгоритмы . arXiv : 1805.01407 .
  17. ^ Перейти обратно: а б «xoshiro/xoroshiro генераторы и перестрелка PRNG» . Проверено 7 сентября 2023 г.
  18. ^ Мацумото, Макото; Вада, Исаку; Курамото, Ай; Ашихара, Хё (сентябрь 2007 г.). «Распространенные дефекты инициализации генераторов псевдослучайных чисел». ACM-транзакции по моделированию и компьютерному моделированию . 17 (4): 15–с. дои : 10.1145/1276927.1276928 . S2CID   1721554 .

Дальнейшее чтение

[ редактировать ]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Xorshift&oldid=1220057836"
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: a804447bb94730cdb47a204e1b2ccfb0__1713703560
URL1:https://arc.ask3.ru/arc/aa/a8/b0/a804447bb94730cdb47a204e1b2ccfb0.html
Заголовок, (Title) документа по адресу, URL1:
Xorshift - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)