Генераторы случайных чисел 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 , как предложил Марсалья. [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+ может добиться на порядок меньше отказов, чем 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** — универсальный генератор случайных 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+ примерно на 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 ); }
^
представляет побитовое исключающее ИЛИ и <<
и >>
представляет побитовые сдвиги .Мы сообщаем, что эти скремблированные генераторы систематически не проходят Big Crush — в частности, тесты линейной сложности и матричного ранга, которые обнаруживают линейность — при взятии 32 младших битов в обратном порядке из каждого 64-битного слова.