Теория
PCG (Permuted Congruential Generator, О'Нил 2014) — современный ответ на вопрос «как улучшить LCG». Внутри — обычный 64-битный LCG-шаг: \(state' = state \cdot 6364136223846793005 + inc \bmod 2^{64}\), но наружу выходит не само состояние, а его перестановка XSH-RR: xorshift-high — \(((state \gg 18) \oplus state) \gg 27\), затем циклический поворот на \(state \gg 59\) бит.
Перестановка прячет линейную структуру LCG от статистических тестов: младшие биты LCG традиционно плохи, и поворот перетасовывает их по всему слову. PCG стал default_random_engine в ряде C++-проектов и новым дефолтом NumPy. Идея оказалась настолько удачной, что породила целое семейство генераторов.
Важно: PCG — не криптографический генератор. Перестановка улучшает статистику, но не мешает восстановить состояние по достаточному числу выходов.
Пример с решением
- Условие. Канонический пример из эталона pcg-c: seed 42, inc 54 — первый выход.
- Формула. Инициализация pcg32_srandom (два «прогревающих» шага), затем LCG-шаг и XSH-RR.
- Подстановка. state = 0, inc = 54·2+1 = 109; после прогрева state += 42.
- Вычисление. xorshifted и поворот дают \(\mathrm{0xA15C02B7}\).
- Ответ. 2707161783 — в hex 0xa15c02b7, ровно как в документации pcg-c. Калькулятор с полями по умолчанию выдаёт это значение первым.
Главное
- LCG внутри, перестановка снаружи — статистика без криптостойкости.
- XSH-RR: xorshift-high + поворот на rot бит.
- Канон: seed 42, inc 54 → 0xa15c02b7.