Mobile wallpaper 1
Profile Image of the Author
Xayah Hina
Graphics & Music
News
I'm currently researching on physics-based deep learning.
721 words
4 minutes
[Instant NGP Code Digest - A First Principle Perspective] PCG: Permuted Congruential Generator
2025-11-28
Graphics
NeRF/NGP
/
Probability
UPDATE LOG
  • PCG Implementation (2025-11-28)
  • PCG Definition (2025-11-28)
  • PCG Motivation (2025-11-28)

1. Why Introduce PCG?#

Most random number generators in widespread use today have one of the following problems: [1]

RNG FamilyStatistical QualityPrediction DifficultyReproducible ResultsMultiple StreamsPeriodUseful FeaturesTime PerformanceSpace UsageCode Size & Complexityk-Dimensional Equidistribution
PCG Family🟢 Excellent🟢 Challenging🟢 Yes🟢 Yes (2^63)🟢 Arbitrary🟢 Jump ahead, Distance🟢 Very fast🟢 Very compact🟢 Very small🟢 Arbitrary*
Mersenne Twister🟡 Some Failures🔴 Easy🟢 Yes🔴 No🟢 Huge (2^19937)🟡 Jump ahead🟡 Acceptable🟡 Huge (2 KB)🟡 Complex🟢 623
Arc4Random🟡 Some Issues🟢 Secure🟡 Not Always🔴 No🟢 Huge (2^1699)🔴 No🔴 Slow🟡 Large (0.5 KB)🟡 Complex🔴 No
ChaCha20†🟢 Good🟢 Secure🟢 Yes🟢 Yes (2^128)🟢 2^128🟢 Jump ahead, Distance🔴 Fairly Slow🟡 Plump (0.1 KB)🟡 Complex🔴 No
Minstd (LCG)🔴 Many Issues🔴 Trivial🟢 Yes🔴 No🔴 Tiny < 2^32🟢 Jump ahead, Distance🟡 Acceptable🟢 Very compact🟢 Very small🔴 No
LCG 64/32🔴 Many Issues🟡 Published Algos🟢 Yes🟢 Yes 2^63🟢 Okay 2^64🟢 Jump ahead, Distance🟢 Very fast🟢 Very compact🟢 Very small🔴 No
XorShift 32🔴 Many Issues🔴 Trivial🟢 Yes🔴 No🔴 Small 2^32🟡 Jump ahead🟢 Fast🟢 Very compact🟢 Very small🔴 No
XorShift 64🔴 Many Issues🔴 Trivial🟢 Yes🔴 No🟢 Okay 2^64🟡 Jump ahead🟢 Fast🟢 Very compact🟢 Very small🔴 No
RanQ🟡 Some Issues🔴 Trivial🟢 Yes🔴 No🟢 Okay 2^64🟡 Jump ahead🟢 Fast🟢 Very compact🟢 Very small🔴 No
XorShift* 64/32🟢 Excellent🟡 Unknown?🟢 Yes🔴 No🟢 Okay 2^64🟡 Jump ahead🟢 Fast🟢 Very compact🟢 Very small🔴 No

2. What is PCG? Learn PCG from Scratch#

2.1 The foundation: LCG [2]#

The most basic PRNG [3] uses this recurrence:

xn+1=(axn+c) mod 264x_{n+1} = (a x_n + c) \bmod 2^{64}

This is only integer modular arithmetic. xn=internal hidden statex_n = \text{internal hidden state}.

It is fast, but it has huge weaknesses:

ProblemWhy
Poor randomnessBits are highly correlated
Easy to predictGiven a few outputs → recover the sequence
Low quality high-order entropyTop bits & bottom bits are uneven

PCG starts from this formula, but enhances it.

2.2 PCG = LCG + Permutation#

Key idea:#

Instead of returning the state directly, apply a randomizing permutation to it.

output=Π(xn)\text{output} = \Pi\big(x_{n}\big)

where Π\Pi scrambles bits to break patterns.

So PCG is:

xn+1=(axn+c) mod 264(LCG update)x_{n+1} = (a x_n + c) \bmod 2^{64} \quad \text{(LCG update)}yn=permute(xn)(XSH-RR bit scramble)y_n = \text{permute}(x_n) \quad \text{(XSH-RR bit scramble)}

PCG doesn’t rely on a stronger LCG— it relies on a brilliant output function.

Permutation in PCG#

Key properties we want of this permutation:

PropertyMeaning
bijectiveevery 64-bit input maps to a unique 64-bit output
nonlinearbreaks the linear structure of LCG outputs
statistically strongspreads entropy across bits
predictable only with effortincreases difficulty of state recovery

The specific permutation used in PCG-XSH-RR (the standard version) is a combination of XOR-shift, high-bit extraction, and a data-dependent bit rotation:

Step 1 — XOR-Shift (XSH)#

Mix the state with a shifted copy of itself:

z=xn⊕(xn≫18)z = x_n \oplus (x_n \gg 18)z=z≫27z = z \gg 27

This step reduces 64-bit state to a scrambled 32-bit value while blending high bits into low bits — eliminating weak low-bit structure of raw LCG.

Step 2 — Random Rotate (RR)#

Compute a rotation amount using the high bits of the state:

r=xn≫59r = x_n \gg 59

Then rotate the previous output value right by that amount:

yn=(z≫r);∣;(z≪(32−r))y_n = (z \gg r) ;\big|; (z \ll (32-r))

This rotation is state-dependent, meaning each output is shuffled differently.

3. PCG: From Theory to Implementation#

3.1 Precise Definition#

Using everything above, we can now define a PCG generator precisely. [4]

A PCG generator is fully determined by two components:

  1. State transition function (LCG core)
  2. Output permutation function (scrambler)

Formally:

xn+1=(axn+c) mod 264yn=Π(xn)\boxed{ \begin{aligned} x_{n+1} &= (a x_n + c) \bmod 2^{64} \\ y_n &= \Pi(x_n) \end{aligned} }

Where:

SymbolMeaning
xnx_n64-bit internal state (never returned directly)
aamultiplier constant, odd, fixed per RNG instance
ccincrement constant (stream selector), must be odd
Π(⋅)\Pi(\cdot)output permutation for statistical quality
yny_nthe returned random number

This structure is modular: any LCG + any permutation = a PCG variant.

The most common and recommended version is PCG-XSH-RR 64/32 → 64-bit state, produces 32-bit outputs.

3.2 Official PCG-XSH-RR Output Function#

Π(x)=ROR((x⊕(x≫18))≫27,;x≫59)\Pi(x) = \text{ROR}\big((x \oplus (x \gg 18)) \gg 27, ; x \gg 59 \big)

Expanded step-by-step:

StepOperation
t=x≫18t = x \gg 18extract high bits
t=x⊕tt = x \oplus tmix entropy (XOR-shift)
z=t≫27z = t \gg 27compress to 32 bits
r=x≫59r = x \gg 59derive rotation amount
y=ROR(z,r)y = \text{ROR}(z, r)final non-linear permutation

Result:

yn=ROR((xn⊕(xn≫18))≫27, xn≫59)\boxed{y_n = \text{ROR}\Big(\big(x_n \oplus (x_n \gg 18)\big) \gg 27,\ x_n \gg 59\Big)}

This is the heart of PCG.

3.3 Official Reference Implementation (C++)#

uint32_t pcg32_random_r(uint64_t& state, uint64_t inc) {
    uint64_t old = state;
    state = old * 6364136223846793005ULL + (inc | 1ULL);


    uint32_t xorshifted = ((old >> 18u) ^ old) >> 27u;
    uint32_t rot = old >> 59u;


    return (xorshifted >> rot) | (xorshifted << ((32 - rot) & 31));
}

Notes:#

  • state evolves using LCG step
  • xorshifted implements the XSH algorithm
  • rot comes from the 59 highest bits
  • final line is the RR rotation → the output

This is exactly the formula we defined above.

Reference#

  1. https://www.pcg-random.org/
  2. https://en.wikipedia.org/wiki/Linear_congruential_generator
  3. https://en.wikipedia.org/wiki/Pseudorandom_number_generator
  4. https://en.wikipedia.org/wiki/Permuted_congruential_generator

Some information may be outdated

[FLUX.2] LoRA Training
[Instant NGP Code Digest - A First Principle Perspective] CDF: Cumulative Distribution Function
© 2025 Xayah Hina.
Powered by Astro & Mizuki  Version 6.1