stringtranslate.com

Ксоршифт

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

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

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

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

Здесь приведена версия C [a] трех алгоритмов 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 ; };    /* Состояние должно быть инициализировано ненулевым значением */ uint32_t xorshift32 ( struct xorshift32_state * state ) { /* Алгоритм «xor» из стр. 4 Марсальи, «ГСЧ Xorshift» */ uint32_t x = state -> a ; х ^= х << 13 ; х ^= х >> 17 ; х ^= х << 5 ; вернуть состояние -> a = x ; }                     struct xorshift64_state { uint64_t a ; };    uint64_t xorshift64 ( struct xorshift64_state * state ) { uint64_t x = состояние -> a ; х ^= х << 13 ; х ^= х >> 7 ; х ^= х << 17 ; вернуть состояние -> a = x ; }                     /* struct xorshift128_state альтернативно может быть определена как пара  uint64_t или uint128_t, если это поддерживается */ struct xorshift128_state { uint32_t x [ 4 ]; };    /* Состояние должно быть инициализировано ненулевым */ uint32_t xorshift128 ( struct xorshift128_state * state ) { /* Алгоритм «xor128» из стр. 5 Марсальи, «ГСЧ Xorshift» */ uint32_t t = state -> x [ 3 ]; uint32_t s = состояние -> x [ 0 ]; /* Выполняем надуманный 32-битный сдвиг. */ состояние -> x [ 3 ] = состояние -> x [ 2 ]; состояние -> х [ 2 ] = состояние -> х [ 1 ]; состояние -> Икс [ 1 ] = s ;                  т ^= т << 11 ; т ^= т >> 8 ; состояние возврата -> 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 = состояние -> a ; х ^= х << 7 ; х ^= х >> 9 ; вернуть состояние -> 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 счетчик ; };      /* Массив состояний должен быть инициализирован так, чтобы первые четыре слова не были нулевыми */ uint32_t xorwow ( struct xorwow_state * state ) { /* Алгоритм «xorwow» из p. 5 Марсальи, «ГСЧ Xorshift» */ uint32_t t = state -> x [ 4 ]; uint32_t s = состояние -> x [ 0 ]; /* Выполняем надуманный 32-битный сдвиг. */ состояние -> x [ 4 ] = состояние -> x [ 3 ]; состояние -> х [ 3 ] = состояние -> х [ 2 ]; состояние -> х [ 2 ] = состояние -> х [ 1 ]; состояние -> Икс [ 1 ] = s ; т ^= т >> 2 ; т ^= т << 1 ; т ^= s ^ ( s << 4 ); состояние -> Икс [ 0 ] = т ; состояние -> счетчик += 362437 ; вернуть t + состояние -> счетчик ; }

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

xorshift*

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

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

#include <stdint.h> /* xorshift64s, вариант A_1(12,25,27) с множителем M_32 из строки 3 таблицы 5 */ uint64_t xorshift64star ( void ) { /* начальное начальное число должно быть ненулевым, не используйте статическую переменную для состояния, если многопоточная */ static uint64_t x = 1 ; х ^= х >> 12 ; х ^= х << 25 ; х ^= х >> 27 ; вернуть х * 0x2545F4914F6CDD1DULL ; }

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

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

#include <stdint.h> /* Состояние должно быть заполнено так, чтобы в массиве был хотя бы один ненулевой элемент */ struct xorshift1024s_state { uint64_t x [ 16 ]; индекс интервала ; };    uint64_t xorshift1024s ( struct xorshift1024s_state * state ) { int index = состояние -> индекс ; uint64_t const s = состояние -> x [ индекс ++ ]; uint64_t t = состояние -> x [ индекс &= 15 ]; т ^= т << 31 ; // а т ^= т >> 11 ; // b -- Опять же, сдвиги и множители настраиваются t ^= s ^ ( s >> 30 ); // состояние c -> x [ индекс ] = 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 ]; };    /* Состояние должно быть заполнено так, чтобы оно не было полностью нулевым */ uint64_t xorshift128p ( struct xorshift128p_state * state ) { uint64_t t = state -> x [ 0 ]; uint64_t const s = состояние -> x [ 1 ]; состояние -> Икс [ 0 ] = s ; т ^= т << 23 ; // а т ^= т >> 18 ; // b -- Опять же, сдвиги и множители настраиваются t ^= s ^ ( s >> 5 ); // состояние c -> x [ 1 ] = t ; вернуть т + с ; }

Хоширо

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

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

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

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

xoshiro256**

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

/* Адаптировано из кода, размещенного на веб-сайте Себастьяно Винья */#include <stdint.h> uint64_t rol64 ( uint64_t x , int k ) { return ( x << k ) | ( х >> ( 64 - к )); }             struct xoshiro256ss_state { uint64_t s [ 4 ]; };   uint64_t xoshiro256ss ( struct xoshiro256ss_state * state ) { uint64_t * s = состояние -> 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 ] ^= т ; с [ 3 ] = rol64 ( с [ 3 ], 45 );     вернуть результат ; }

xoshiro256+

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

#include <stdint.h> uint64_t rol64 ( uint64_t x , int k ) { return ( x << k ) | ( х >> ( 64 - к )); }             struct xoshiro256p_state { uint64_t s [ 4 ]; };   uint64_t xoshiro256p ( struct xoshiro256p_state * state ) { uint64_t * s = состояние -> 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 ] ^= т ; с [ 3 ] = rol64 ( с [ 3 ], 45 );     вернуть результат ; }

Соросиро

Если пространство ограничено, 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 * состояние ) { uint64_t результат = ( состояние -> s += 0x9E3779B97f4A7C15 ); результат = ( результат ^ ( результат >> 30 )) * 0xBF58476D1CE4E5B9 ; результат = ( результат ^ ( результат >> 27 )) * 0x94D049BB133111EB ; вернуть результат ^ ( результат >> 31 ); }                              struct xorshift128_state { uint32_t x [ 4 ]; };    // то же самое можно сделать и для любого другого генератора void xorshift128_init ( struct xorshift128_state * state , uint64_t семя ) { struct Splitmix64_state smstate = { seed };          uint64_t tmp = Splitmix64 ( & smstate ); состояние -> x [ 0 ] = ( uint32_t ) tmp ; состояние -> x [ 1 ] = ( uint32_t )( tmp >> 32 );         tmp = Splitmix64 ( & smstate ); состояние -> x [ 2 ] = ( uint32_t ) tmp ; состояние -> x [ 3 ] = ( uint32_t )( tmp >> 32 ); }

Примечания

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

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

  1. ^ abc Марсалья, Джордж (июль 2003 г.). «Xorshift ГСЧ». Журнал статистического программного обеспечения . 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. ^ abcd Лемир, Дэниел; О'Нил, Мелисса Э. (апрель 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. ^ «ISO/IEC 60559:2020». ИСО .
  7. ↑ Ле Флок, Фабьен (12 января 2011 г.). «Результаты XORWOW L'ecuyer TestU01» . В погоне за дьяволом (блог) . Проверено 2 ноября 2017 г.
  8. ^ "Тестирование cuRAND" . Нвидия . Проверено 2 ноября 2017 г.
  9. ^ abc Винья, Себастьяно (июль 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. ^ ab "генераторы xoshiro/xoroshiro и перестрелка PRNG" . Проверено 7 сентября 2023 г.
  18. ^ Мацумото, Макото; Вада, Исаку; Курамото, Ай; Ашихара, Хё (сентябрь 2007 г.). «Распространенные дефекты инициализации генераторов псевдослучайных чисел». ACM Transactions по моделированию и компьютерному моделированию . 17 (4): 15–с. дои : 10.1145/1276927.1276928. S2CID  1721554.

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