Xorshift - Xorshift

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

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

Генераторы Xorshift - одни из самых быстрыхкриптографически безопасные генераторы случайных чисел, требуя очень небольшого кода и состояния. Хотя они не проходят все статистические тесты без дальнейшего уточнения, эта слабость хорошо известна и легко исправляется (как указано Марсалья в исходной статье) путем объединения их с нелинейной функцией, в результате чего получается, например, в генераторе xorshift + или xorshift *. Собственная реализация генератора xorshift + на языке C, который проходит все тесты из набора BigCrush (с на порядок меньше сбоев, чем Мерсенн Твистер или же ЧТО Ж ) обычно занимает менее 10 тактов на x86 для генерации случайного числа благодаря конвейерная обработка инструкций.^[4]

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

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

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

А C версия^{[примечание 1]} трех алгоритмов xorshift^[1]:4,5 приводится здесь. Первый имеет одно 32-битное слово состояния и период 2.³²−1. Второй имеет одно 64-битное слово состояния и период 2.⁶⁴−1. Последний имеет четыре 32-битных слова состояния и период 2.¹²⁸−1. Все используют три смены и три или четыре операции исключающего ИЛИ:

#включают <stdint.h>структура xorshift32_state {  uint32_t а;};/ * Слово состояния должно быть инициализировано ненулевым * /uint32_t xorshift32(структура xorshift32_state *государственный){	/ * Алгоритм "xor" из п. 4 Марсальи, "Xorshift RNGs" * /	uint32_t Икс = государственный->а;	Икс ^= Икс << 13;	Икс ^= Икс >> 17;	Икс ^= Икс << 5;	возвращаться государственный->а = Икс;}структура xorshift64_state {  uint64_t а;};uint64_t xorshift64(структура xorshift64_state *государственный){	uint64_t Икс = государственный->а;	Икс ^= Икс << 13;	Икс ^= Икс >> 7;	Икс ^= Икс << 17;	возвращаться государственный->а = Икс;}структура xorshift128_state {  uint32_t а, б, c, d;};/ * Массив состояний должен быть инициализирован, чтобы он не был полностью нулевым * /uint32_t xorshift128(структура xorshift128_state *государственный){	/ * Алгоритм "xor128" из п. 5 Марсальи, "Xorshift RNGs" * /	uint32_t т = государственный->d;	uint32_t const s = государственный->а;	государственный->d = государственный->c;	государственный->c = государственный->б;	государственный->б = s;	т ^= т << 11;	т ^= т >> 8;	возвращаться государственный->а = т ^ s ^ (s >> 19);}

128-битный алгоритм проходит стойкие испытания. Однако он не проходит тесты MatrixRank и LinearComp из набора тестов BigCrush из TestU01 рамки.

Вариации

Все генераторы xorshift не проходят некоторые тесты из TestU01 набор тестов BigCrush. Это верно для всех генераторов, основанных на линейных повторениях, таких как Мерсенн Твистер или же ЧТО Ж. Однако выходной сигнал таких генераторов легко скремблировать, чтобы улучшить их качество.

xorwow

Марсалья предложил скремблировать вывод, комбинируя его с простым аддитивным счетчиком по модулю 2.³² (которую он называет «последовательностью Вейля» после Теорема Вейля о равнораспределении ). Это также увеличивает период в 2 раза.³², до 2¹⁹²−2³²:

#включают <stdint.h>структура xorwow_state {    uint32_t а, б, c, d, е;    uint32_t прилавок;};/ * Массив состояний должен быть инициализирован так, чтобы он не равнялся нулю в первых четырех словах * /uint32_t xorwow(структура xorwow_state *государственный){    / * Алгоритм "xorwow" из п. 5 Марсальи, "Xorshift RNGs" * /    uint32_t т = государственный->е;    uint32_t s = государственный->а;    государственный->е = государственный->d;    государственный->d = государственный->c;    государственный->c = государственный->б;    государственный->б = s;    т ^= т >> 2;    т ^= т << 1;    т ^= s ^ (s << 4);    государственный->а = т;    государственный->прилавок += 362437;    возвращаться т + государственный->прилавок;}

Это работает хорошо, но не проходит несколько тестов в BigCrush.^[6] Этот генератор установлен по умолчанию в Nvidia. CUDA Инструментарий.^[7]

xorshift *

А xorshift * генератор занимает xorshift генератор и применяет обратимое умножение (по модулю размера слова) к его выходным данным как нелинейное преобразование, как было предложено Марсалья.^[1] Следующий 64-битный генератор с 64 битами состояния имеет максимальный период 2⁶⁴−1^[8] и не проходит только тест MatrixRank BigCrush:

#включают <stdint.h>структура xorshift64s_state {  uint64_t а;};uint64_t xorshift64s(структура xorshift64s_state *государственный){	uint64_t Икс = государственный->а;	/ * Состояние должно быть заполнено ненулевым значением. * /	Икс ^= Икс >> 12; // а	Икс ^= Икс << 25; // б	Икс ^= Икс >> 27; // c	государственный->а = Икс;	возвращаться Икс * UINT64_C(0x2545F4914F6CDD1D);}

Аналогичный генератор предлагается в Числовые рецепты^[9] в качестве RanQ1, но он также не проходит тест BirthdaySpacings.

Если генератор модифицирован так, чтобы возвращать только старшие 32 бита, то он проходит BigCrush с нулевым количеством ошибок.^[10]:7 Фактически, сокращенная версия всего с 40 битами внутреннего состояния проходит через пакет, что предполагает большой запас прочности.^[10]:19

Vigna^[8] предлагает следующее xorshift1024 * генератор с 1024 битами состояния и максимальным периодом 2¹⁰²⁴−1; однако он не всегда проходит BigCrush.^[5] Поэтому xoshiro256 ** - гораздо лучший вариант.

#включают <stdint.h>/ * Состояние должно быть заполнено таким образом, чтобы в массиве был хотя бы один ненулевой элемент * /структура xorshift1024s_state {	uint64_t множество[16];	int индекс;};uint64_t xorshift1024s(структура xorshift1024s_state *государственный){	int индекс = государственный->индекс;	uint64_t const s = государственный->множество[индекс++];	uint64_t т = государственный->множество[индекс &= 15];	т ^= т << 31;		// а	т ^= т >> 11;		// б	т ^= s ^ (s >> 30);	// c	государственный->множество[индекс] = т;	государственный->индекс = индекс;	возвращаться т * (uint64_t)1181783497276652981;}

Оба генератора, как это бывает со всеми xorshift * генераторы генерируют последовательность 64-битных значений, которая равнораспределена в максимально возможном измерении (за исключением того, что они никогда не будут выводить ноль для 16 вызовов, то есть 128 байтов, в строке).^[8]

xorshift +

Вместо умножения можно использовать сложение как более быстрое нелинейное преобразование. Идея была впервые предложена Сайто и Мацумото (также ответственными за Мерсенн Твистер ) в генераторе XSadd, который добавляет два последовательных выхода базового xorshift генератор на основе 32-битных сдвигов.^[11]

XSadd, однако, имеет слабые места в младших битах вывода; он не проходит несколько тестов BigCrush, когда выходные слова инвертированы. Чтобы исправить эту проблему, Vigna^[12] представил xorshift + семейство, основанное на 64-битных сдвигах: следующие xorshift128 + генератор использует 128 бит состояния и имеет максимальный период 2¹²⁸−1. Он проходит BigCrush, но не при отмене.^[5]

#включают <stdint.h>структура xorshift128p_state {  uint64_t а, б;};/ * Состояние должно быть заполнено так, чтобы оно не было нулевым * /uint64_t xorshift128p(структура xorshift128p_state *государственный){	uint64_t т = государственный->а;	uint64_t const s = государственный->б;	государственный->а = s;	т ^= т << 23;		// а	т ^= т >> 17;		// б	т ^= s ^ (s >> 26);	// c	государственный->б = т;	возвращаться т + s;}

Этот генератор является одним из самых быстрых генераторов, прошедших BigCrush.^[4] Одним из недостатков добавления последовательных выходов является то, что основной xorshift128 генератор двумерно равнораспределен, связанный xorshift128 + генератор только одномерно равнораспределен.^[12]

Генераторы Xorshift + даже размером xorshift1024 +, демонстрируют заметную линейность в младших битах своего выхода.^[5]

xoshiro и xoroshiro

xoshiro и xoroshiro - это другие варианты генераторов регистра сдвига, использующие вращения в дополнение к сдвигам. По словам Vigna, они быстрее и производят лучшее качество, чем xorshift.^[13][14]

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

xoshiro256 **

xoshiro256 ** - семейный универсальный генератор случайных 64-битных чисел.

/ * Адаптировано из кода, представленного на сайте Себастьяна Виньи * /#включают <stdint.h>uint64_t rol64(uint64_t Икс, int k){	возвращаться (Икс << k) | (Икс >> (64 - k));}структура xoshiro256ss_state {	uint64_t s[4];};uint64_t xoshiro256ss(структура xoshiro256ss_state *государственный){	uint64_t *s = государственный->s;	uint64_t const результат = rol64(s[1] * 5, 7) * 9;	uint64_t const т = s[1] << 17;	s[2] ^= s[0];	s[3] ^= s[1];	s[1] ^= s[2];	s[0] ^= s[3];	s[2] ^= т;	s[3] = rol64(s[3], 45);	возвращаться результат;}

xoshiro256 +

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

#включают <stdint.h>uint64_t rol64(uint64_t Икс, int k){	возвращаться (Икс << k) | (Икс >> (64 - k));}структура xoshiro256p_state {	uint64_t s[4];};uint64_t xoshiro256p(структура xoshiro256p_state *государственный){	uint64_t (*s)[4] = &государственный->s;	uint64_t const результат = s[0] + s[3];	uint64_t const т = s[1] << 17;	s[2] ^= s[0];	s[3] ^= s[1];	s[1] ^= s[2];	s[0] ^= s[3];	s[2] ^= т;	s[3] = rol64(s[3], 45);	возвращаться результат;}

Другие варианты

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

Для 32-битного вывода xoshiro128 ** и xoshiro128 + в точности эквивалентны xoshiro256 ** и xoshiro256 +, с uint32_t вместо uint64_t и с разными константами сдвига / поворота; аналогично xoroshiro64 ** и xoroshiro64 * эквивалентны xoroshiro128 ** и xoroshiro128 + соответственно. В отличие от функций с большим состоянием, xoroshiro64 ** и xoroshiro64 * не являются простыми портами своих аналогов с более высокой точностью.

Совсем недавно генераторы ++ были созданы как альтернатива генераторам **.

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

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

#включают <stdint.h>структура splitmix64_state {	uint64_t s;};uint64_t splitmix64(структура splitmix64_state *государственный) {	uint64_t результат = государственный->s;	государственный->s = результат + 0x9E3779B97f4A7C15;	результат = (результат ^ (результат >> 30)) * 0xBF58476D1CE4E5B9;	результат = (результат ^ (результат >> 27)) * 0x94D049BB133111EB;	возвращаться результат ^ (результат >> 31);}// В качестве примера; можно сделать то же самое для любого другого генератораструктура xorshift128_state xorshift128_init(uint64_t семя) {	структура splitmix64_state smstate = {семя};	структура xorshift128_state результат = {0};	uint64_t tmp = splitmix64(&smstate);	результат.а = (uint32_t)tmp;	результат.б = (uint32_t)(tmp >> 32);	tmp = splitmix64(&smstate);	результат.c = (uint32_t)tmp;	результат.d = (uint32_t)(tmp >> 32);	возвращаться результат;}

Примечания

1. В C и большинстве других языков на основе C каретка (^) представляет собой побитовое XOR, и " << " и " >> "операторы представляют левую и правую побитовые сдвиги, соответственно.

Рекомендации

1. Марсалья, Джордж (Июль 2003 г.). "Xorshift RNGs". Журнал статистического программного обеспечения. 8 (14). Дои:10.18637 / jss.v008.i14.
2. Брент, Ричард П. (Август 2004 г.). «Заметка о генераторах случайных чисел Xorshift Марсаглии». Журнал статистического программного обеспечения. 11 (5). Дои:10.18637 / jss.v011.i05.
3. Паннетон, Франсуа; L'Ecuyer, Пьер (октябрь 2005 г.). «О генераторах случайных чисел xorshift» (PDF). Транзакции ACM по моделированию и компьютерному моделированию. 15 (4): 346–361. Дои:10.1145/1113316.1113319. S2CID  11136098.
4. Винья, Себастьяно. "xorshift * / xorshift + генераторы и перестрелка ГПСЧ". Получено 2014-10-25.
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. Ле Флок, Фабьен (12 января 2011 г.). "Результаты XORWOW L'ecuyer TestU01". Погоня за дьяволом (блог). Получено 2017-11-02.
7. "Тестирование cuRAND". Nvidia. Получено 2017-11-02.
8. Винья, Себастьяно (июль 2016 г.). "Экспериментальное исследование генераторов xorshift Марсальи в зашифрованном виде" (PDF). Транзакции ACM на математическом ПО. 42 (4): 30. arXiv:1402.6246. Дои:10.1145/2845077. S2CID  13936073. Предлагает генераторы xorshift *, добавляя окончательное умножение на константу.
9. Пресс, WH; Теукольский, С.А.; Феттерлинг, штат Вашингтон; Фланнери, ВР (2007). «Раздел 7.1.2.A. 64-битный метод Xorshift». Числовые рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN  978-0-521-88068-8.
10. О'Нил, Мелисса Э. (5 сентября 2014 г.). PCG: семейство простых быстрых, эффективных с точки зрения пространства, статистически хороших алгоритмов для генерации случайных чисел (PDF) (Технический отчет). Колледж Харви Мадда. С. 6–8. HMC-CS-2014-0905.
11. Сайто, Муцуо; Мацумото, Макото (2014). «XORSHIFT-ADD (XSadd): вариант XORSHIFT». Получено 2014-10-25.
12. Винья, Себастьяно (май 2017 г.). "Дальнейшее копирование генераторов xorshift Марсальи" (PDF). Журнал вычислительной и прикладной математики. 315 (C): 175–181. arXiv:1404.0390. Дои:10.1016 / j.cam.2016.11.006. S2CID  6876444. Описывает генераторы xorshift +, обобщение XSadd.
13. Винья, Себастьяно. "Генераторы xoshiro / xoroshiro и перестрелка ГПСЧ". Получено 2019-07-07.
14. Блэкман, Дэвид; Винья, Себастьяно (2018). "Шифрованные линейные генераторы псевдослучайных чисел". arXiv:1805.01407.
15. Мацумото, Макото; Вада, Исаку; Курамото, Ай; Ашихара, Хё (сентябрь 2007 г.). «Распространенные ошибки при инициализации генераторов псевдослучайных чисел». Транзакции ACM по моделированию и компьютерному моделированию. 17 (4): 15 – es. Дои:10.1145/1276927.1276928. S2CID  1721554.

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

• Брент, Ричард П. (Июль 2006 г.). «Некоторые генераторы долгопериодических случайных чисел, использующие сдвиги и xors». Журнал ANZIAM. 48: C188 – C202. Список генераторов различных размеров с четырьмя сменами (по две на слово обратной связи).