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

Конгруэнтный генератор с перестановками ( PCG ) — это генерации псевдослучайных чисел алгоритм , разработанный в 2014 году доктором М. Е. О'Нилом, который применяет функцию перестановки выходных данных для улучшения статистических свойств числа по модулю 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 -1 бит используются для величины поворота, следующие по значимости 2 ^{б -1} биты поворачиваются вправо и используются в качестве выходных, а младшие 2 ^{б -1}Биты +1- b отбрасываются.
RS: Случайный (зависящий от ввода) сдвиг для случаев, когда ротация обходится дороже. Опять же, выходной размер вдвое меньше входного. Начиная с 2 ^б-битовое входное слово, старшие b -3 бита используются для величины сдвига, которая применяется к следующим по значимости 2 ^{б -1}+2 ^{б -3}−1 бит и наименее значимые 2 ^{б -1} выводятся биты результата. Низкий 2 ^{б -1}−2 ^{б -3}− b +4 бита отбрасываются.
XSH: операция xorshift , x ^= x >> constant. Константа выбирается равной половине битов, не отброшенных следующей операцией (округленной в меньшую сторону).
XSL: упрощенная версия xorshift, складывающая значение пополам путем XOR старшей половины к младшей. Свернутое значение используется для последующих вращений.
RXS: xorshift на случайную (зависящую от ввода) величину.
М: Умножение на фиксированную константу.

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

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 ¹²⁸ Если требуется, генератор можно расширить с помощью массива подгенераторов. Один из них выбирается (по очереди) для добавления к выходу основного генератора, и каждый раз, когда состояние основного генератора достигает нуля, подгенераторы запускаются по шаблону, который обеспечивает экспоненциальную периодичность в общем размере состояния.

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

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

#include <stdint.h>
static uint64_t       state      = 0x4d595df4d0f33173;		// Or something seed-dependent
static uint64_t const multiplier = 6364136223846793005u;
static uint64_t const increment  = 1442695040888963407u;	// Or an arbitrary odd constant

static uint32_t rotr32(uint32_t x, unsigned r)
{
	return x >> r | x << (-r & 31);
}

uint32_t pcg32(void)
{
	uint64_t x = state;
	unsigned count = (unsigned)(x >> 59);		// 59 = 64 - 5

	state = x * multiplier + increment;
	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;	// Must be odd
static uint64_t const multiplier = 6364136223846793005u;

uint32_t pcg32_fast(void)
{
	uint64_t x = mcg_state;
	unsigned count = (unsigned)(x >> 61);	// 61 = 64 - 3

	mcg_state = x * multiplier;
	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 бита), поэтому предпочтительна обычная версия, за исключением extremis . Тем не менее, эта более быстрая версия также проходит статистические тесты. ^[4]

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

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

Мелисса О'Нил предлагает тестировать ГПСЧ, применяя статистические тесты к их вариантам уменьшенного размера и определяя минимальное количество бит внутреннего состояния, необходимое для прохождения. ^[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 и Твистер Мерсенна терпит неудачу, несмотря на 19937 бит состояния. ^[9]

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

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

См. также [ править ]

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

Ссылки [ править ]

^ Лемир, Дэниел (22 августа 2017 г.). «Тестирование некриптографических генераторов случайных чисел: мои результаты» . Проверено 3 октября 2017 г.
^ Кук, Джон Д. (7 июля 2017 г.). «Тестирование генератора случайных чисел PCG» . Проверено 3 октября 2017 г.
^ Кук, Джон Д. (14 августа 2017 г.). «Тестирование ГСЧ с помощью PractRand» . Проверено 3 октября 2017 г.
↑ Перейти обратно: Перейти обратно: ^а ^б О'Нил, Мэн (29 июля 2017 г.). «PCG прошла PractRand» . Проверено 3 ноября 2017 г.
↑ Перейти обратно: Перейти обратно: ^а ^б ^с ^д ^и ^ж О'Нил, Мелисса Э. (5 сентября 2014 г.). PCG: семейство простых быстрых и статистически эффективных алгоритмов генерации случайных чисел (PDF) (технический отчет). Колледж Харви Мадда . HMC-CS-2014-0905.
↑ Перейти обратно: Перейти обратно: ^а ^б О'Нил, Мэн (10 августа 2017 г.). «Критика стримов PCG (и SplitMix тоже)» . Проверено 3 ноября 2017 г.
^ О'Нил, Мэн (20 августа 2017 г.). «Визуализация сути некоторых ГПСЧ» . Проверено 3 ноября 2017 г.
^ О'Нил, Мэн (20 августа 2017 г.). «Слишком большой, чтобы потерпеть неудачу» . Проверено 3 ноября 2017 г.
^ Л'Экуйер, Пьер; Симард, Ричард (август 2007 г.). «TestU01: библиотека AC для эмпирического тестирования генераторов случайных чисел» (PDF) . Транзакции ACM в математическом программном обеспечении . 33 (4): 22-1–22-40. CiteSeerX 10.1.1.499.2830 . дои : 10.1145/1268776.1268777 . S2CID 273446 .
^ Буйаге, Шарль; Мартинес, Флоретт; Соваж, Джулия (28 сентября 2020 г.). «Практическое восстановление начального числа для генератора псевдослучайных чисел PCG». Транзакции IACR по симметричной криптологии . 2020 (3): 175–196. дои : 10.13154/tosc.v2020.i3.175-196 . S2CID 222137612 .

Внешние ссылки [ править ]

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

[1] Лемир, Дэниел (22 августа 2017 г.). «Тестирование некриптографических генераторов случайных чисел: мои результаты» . Проверено 3 октября 2017 г.

[2] Кук, Джон Д. (7 июля 2017 г.). «Тестирование генератора случайных чисел PCG» . Проверено 3 октября 2017 г.

[3] Кук, Джон Д. (14 августа 2017 г.). «Тестирование ГСЧ с помощью PractRand» . Проверено 3 октября 2017 г.

[pcg-passes-4] Перейти обратно: Перейти обратно: ^а ^б О'Нил, Мэн (29 июля 2017 г.). «PCG прошла PractRand» . Проверено 3 ноября 2017 г.

[ONeill-5] Перейти обратно: Перейти обратно: ^а ^б ^с ^д ^и ^ж О'Нил, Мелисса Э. (5 сентября 2014 г.). PCG: семейство простых быстрых и статистически эффективных алгоритмов генерации случайных чисел (PDF) (технический отчет). Колледж Харви Мадда . HMC-CS-2014-0905.

[critiquing-6] Перейти обратно: Перейти обратно: ^а ^б О'Нил, Мэн (10 августа 2017 г.). «Критика стримов PCG (и SplitMix тоже)» . Проверено 3 ноября 2017 г.

[7] О'Нил, Мэн (20 августа 2017 г.). «Визуализация сути некоторых ГПСЧ» . Проверено 3 ноября 2017 г.

[8] О'Нил, Мэн (20 августа 2017 г.). «Слишком большой, чтобы потерпеть неудачу» . Проверено 3 ноября 2017 г.

[9] Л'Экуйер, Пьер; Симард, Ричард (август 2007 г.). «TestU01: библиотека AC для эмпирического тестирования генераторов случайных чисел» (PDF) . Транзакции ACM в математическом программном обеспечении . 33 (4): 22-1–22-40. CiteSeerX 10.1.1.499.2830 . дои : 10.1145/1268776.1268777 . S2CID 273446 .

[10] Буйаге, Шарль; Мартинес, Флоретт; Соваж, Джулия (28 сентября 2020 г.). «Практическое восстановление начального числа для генератора псевдослучайных чисел PCG». Транзакции IACR по симметричной криптологии . 2020 (3): 175–196. дои : 10.13154/tosc.v2020.i3.175-196 . S2CID 222137612 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]