Переставленный конгруэнтный генератор

Пермутируемый конгруэнтный генератор ( PCG ) — это алгоритм генерации псевдослучайных чисел, разработанный в 2014 году доктором ME O'Neill, который применяет выходную функцию перестановки для улучшения статистических свойств линейного конгруэнтного генератора по модулю 2 ⁿ . Он достигает превосходной статистической производительности ^{[1] [2] [3] [4]} с небольшим и быстрым кодом и малым размером состояния. ^[5]

PCG отличается от классического линейного конгруэнтного генератора (LCG) тремя особенностями:

• модуль и состояние LCG больше, обычно в два раза больше желаемого выходного значения,
• он использует модуль степени 2 , что приводит к особенно эффективной реализации с генератором полного периода и несмещенными выходными битами, и
• состояние не выводится напрямую, а наиболее значимые биты состояния используются для выбора побитового вращения или сдвига, который применяется к состоянию для получения выходных данных.

Именно переменное вращение устраняет проблему короткого периода в младших битах, от которой страдают LCG степени 2. ^{[5] : 31–34}

Варианты

Семейство PCG включает ряд вариантов. Основной LCG определен для ширины от 8 до 128 бит ^{[ требуется ссылка ]} , хотя для практического использования рекомендуются только 64 и 128 бит; меньшие размеры предназначены для статистических тестов техники.

Аддитивная константа в LCG может изменяться для создания различных потоков. Константа представляет собой произвольное нечетное целое число, ^[6], поэтому ее не нужно хранить явно; можно использовать адрес самой переменной состояния (с установленным младшим битом).

Определено несколько различных выходных преобразований. Все они работают хорошо, но некоторые имеют больший запас, чем другие. ^{[5] : 39} Они построены из следующих компонентов:

• RR: Случайный (зависящий от входа) поворот с выходом в два раза меньше входного. При наличии 2 ^b -битного входного слова верхние b −1 бит используются для величины поворота, следующие по значимости 2 ^{b −1} бит поворачиваются вправо и используются в качестве выхода, а нижние 2 ^{b −1} +1− b бит отбрасываются.
• RS: Случайный (зависящий от входа) сдвиг для случаев, когда повороты более затратны. Опять же, выходной сигнал имеет размер, равный половине входного сигнала. Начиная с 2 ^b -битного входного слова, верхние b −3 бита используются для величины сдвига, которая применяется к следующим по значимости 2 ^{b −1} +2 ^{b −3} −1 битам, а младшие 2 ^{b −1} биты результата выводятся. Нижние 2 ^{b −1} −2 ^{b −3} − b +4 бита отбрасываются.
• XSH: Операция xorshift , x ^= x >> constant. Константа выбирается равной половине битов, не отброшенных следующей операцией (округленных в меньшую сторону).
• XSL: Упрощенная версия xorshift, складывающая значение пополам с помощью XOR высокой половины в низкую. Сложенное значение используется для последующих вращений.
• RXS: Сдвиг на случайную (зависящую от входных данных) величину.
• М: Умножение на фиксированную константу.

Они объединены в следующие рекомендуемые выходные преобразования, проиллюстрированные здесь в наиболее распространенных размерах:

• XSH-RR: Xorshift смешивает некоторые старшие биты вниз, затем биты 63–59 выбирают величину поворота, которая будет применена к битам 27–58.

  (64→32 бита) count = (int)(x >> 59); x ^= x >> 18; return rotr32((uint32_t)(x >> 27), count); .

• XSH-RS: Аналогично, но для выбора величины сдвига используется меньшее количество бит.

  (64→32 бита) count = (int)(x >> 61); x ^= x >> 22; return (uint32_t)(x >> (29 - count)); .

• XSL-RR: упрощенная версия XSH-RR, оптимизированная для 128-битных состояний, реализованная с использованием двух слов на 64-битных машинах.

  (128→64 бита) count = (int)(x >> 122); x64 = (uint64_t)(x ^ (x >> 64)); return rotr64(x64, count);

• RXS-M-XS: Самое медленное и сильное преобразование выходных данных при использовании для получения выходных данных половинного размера, оно становится самым слабым при использовании по назначению, для получения выходных данных того же размера, что и состояние. Для использования, когда размер состояния должен быть ограничен 32 или 64 битами.

  (32→32 бита) count=(int)(x >> 28); x ^= x >> (4 + count); x *= 277803737u; return x ^ (x >> 22);

  (64→64 бита) count=(int)(x >> 59); x ^= x >> (5 + count); x *= 12605985483714917081u; return x ^ (x >> 43);

• XSL-RR-RR: Подобно предыдущему, этот метод преобразует 128 бит состояния в 128 бит вывода, когда это требуется приложению.

  (128→128 бит) count = (int)(x >> 122); low64 = rotr64((uint64_t)(x ^ (x >> 64)), count); high64 = rotr64((uint64_t)(x >> 64), low64 & 63); return (uint128_t)high64 << 64 | low64;

Каждый шаг этих выходных преобразований либо обратим (и, следовательно, один к одному ), либо является усечением, поэтому их композиция отображает одно и то же фиксированное число входных состояний в каждое выходное значение. Это сохраняет равнораспределение базового LCG.

Наконец, если требуется длина цикла больше 2 ^{128 , генератор может быть} расширен массивом подгенераторов. Один выбирается (по очереди) для добавления к выходу основного генератора, и каждый раз, когда состояние основного генератора достигает нуля, подгенераторы циклически запускаются по шаблону, который обеспечивает период, экспоненциальный по общему размеру состояния.

Пример кода

Генератор, рекомендуемый для большинства пользователей ^{[5] : 43} — это PCG-XSH-RR с 64-битным состоянием и 32-битным выходом. Его можно реализовать как:

#include <stdint.h> static uint64_t state = 0x4d595df4d0f33173 ; // Или что-то зависящее от семени static uint64_t const multiplier = 6364136223846793005u ; static uint64_t const increment = 1442695040888963407u ; // Или произвольная нечетная константа               статический uint32_t rotr32 ( uint32_t x , беззнаковый r ) { return x >> r | x << ( - r & 31 ); }              uint32_t pcg32 ( void ) { uint64_t x = state ; беззнаковое количество = ( беззнаковое )( x >> 59 ); // 59 = 64 - 5         состояние = x * множитель + приращение ; x ^= x >> 18 ; // 18 = (64 - 27)/2 return rotr32 (( uint32_t )( x >> 27 ), count ); // 27 = 32 - 5 }              void pcg32_init ( uint64_t seed ) { state = seed + increment ; ( void ) pcg32 (); }      

Генератор применяет выходное преобразование к начальному состоянию, а не к конечному , чтобы увеличить доступный параллелизм на уровне инструкций и максимизировать производительность на современных суперскалярных процессорах . ^{[5] : 43}

Немного более быстрая версия устраняет приращение, сводя LCG к мультипликативному генератору ( в стиле Лемера ) с периодом всего 2 ⁶² и использует более слабую выходную функцию XSH-RS:

static uint64_t mcg_state = 0xcafef00dd15ea5e5u ; // Должно быть нечетным static uint64_t const multiplier = 6364136223846793005u ;         uint32_t pcg32_fast ( void ) { uint64_t x = mcg_state ; беззнаковое число = ( беззнаковое )( x >> 61 ); // 61 = 64 - 3         mcg_state = x * множитель ; x ^= x >> 22 ; return ( uint32_t )( x >> ( 22 + count )); // 22 = 32 - 3 - 7 }             void pcg32_fast_init ( uint64_t seed ) { mcg_state = 2 * seed + 1 ; ( void ) pcg32_fast (); }      

Экономия времени минимальна, так как самая дорогая операция (умножение 64×64 бит) остается, поэтому предпочтительнее использовать обычную версию, за исключением крайних случаев . Тем не менее, эта более быстрая версия также проходит статистические тесты. ^[4]

При выполнении на 32-битном процессоре 64×64-битное умножение должно быть реализовано с использованием трех операций умножения 32×32→64-бит. Чтобы сократить это число до двух, существуют 32-битные умножители, которые работают почти так же хорошо, как 64-битные, например, 0xf13283ad ^[6] , 0xffffffff0e703b65 или 0xf2fc5985.

Сравнение с другими генераторами псевдослучайных чисел

Мелисса О'Нил предлагает тестировать PRNG, применяя статистические тесты к их уменьшенным вариантам и определяя минимальное количество внутренних битов состояния, необходимых для прохождения. ^{[7] BigCrush} от TestU01 проверяет достаточно данных, чтобы обнаружить период 2 ³⁵ , поэтому даже идеальному генератору требуется 36 бит состояния, чтобы пройти его. Некоторые очень плохие генераторы могут пройти, если им дать достаточно большое состояние; ^[8] прохождение, несмотря на малое состояние, является мерой качества алгоритма и показывает, насколько велик запас прочности между этим нижним пределом и размером состояния, используемым в практических приложениях.

PCG-RXS-M-XS (с 32-битным выходом) проходит BigCrush с 36 битами состояния (минимально возможный), PCG-XSH-RR ( pcg32()выше) требует 39, а PCG-XSH-RS ( pcg32_fast()выше) требует 49 бит состояния. Для сравнения, xorshift* , одна из лучших альтернатив, требует 40 бит состояния, ^{[5] : 19} и Mersenne twister терпит неудачу, несмотря на 19937 бит состояния. ^[9]

Прогнозирование и восстановление семян

Было показано, что практически возможно (с большим объемом вычислений) восстановить начальное число псевдослучайного генератора, имея 512 последовательных выходных байтов. ^[10] Это означает, что практически возможно предсказать остальную часть псевдослучайного потока, имея 512 байтов.

Смотрите также

• Полный цикл
• xoroshiro128+ , xoroshiro128**, xoshiro256+, xoshiro256** — семейство конкурентов

Ссылки

1. Лемир, Дэниел (22 августа 2017 г.). "Тестирование некриптографических генераторов случайных чисел: мои результаты" . Получено 03.10.2017 .
2. Кук, Джон Д. (7 июля 2017 г.). "Тестирование генератора случайных чисел PCG" . Получено 03.10.2017 .
3. Кук, Джон Д. (14 августа 2017 г.). "Тестирование ГСЧ с помощью PractRand" . Получено 03.10.2017 .
4. O'Neill, ME (29 июля 2017 г.). "PCG Passes PractRand" . Получено 2017-11-03 .
5. О'Нил, Мелисса Э. (5 сентября 2014 г.). PCG: Семейство простых быстрых и эффективных по объему статистически хороших алгоритмов для генерации случайных чисел (PDF) (Технический отчет). Колледж Харви Мадда . HMC-CS-2014-0905.
6. O'Neill, ME (10 августа 2017 г.). "Критика потоков PCG (и SplitMix тоже)" . Получено 2017-11-03 .
7. О'Нил, ME (20 августа 2017 г.). "Визуализация сердца некоторых PRNG" . Получено 2017-11-03 .
8. O'Neill, ME (20 августа 2017 г.). "Too Big to Fail" . Получено 03.11.2017 .
9. L'Ecuyer, Pierre; Simard, Richard (август 2007 г.). "TestU01: библиотека AC для эмпирического тестирования генераторов случайных чисел" (PDF) . ACM Transactions on Mathematical Software . 33 (4): 22-1–22-40. CiteSeerX 10.1.1.499.2830 . doi :10.1145/1268776.1268777. S2CID  273446. 
10. Буйаге, Чарльз; Мартинес, Флоретт; Соваж, Джулия (28 сентября 2020 г.). «Практическое восстановление начального значения для генератора псевдослучайных чисел PCG». Труды IACR по симметричной криптологии . 2020 (3): 175–196. doi :10.13154/tosc.v2020.i3.175-196. S2CID  222137612.

Внешние ссылки

• PCG, семейство лучших генераторов случайных чисел. Веб-сайт
• PCG, семейство лучших генераторов случайных чисел — вдохновлено /r/programming! Обсуждение автора на Reddit