Randomness & NoiseRND-01
PCG (Random Numbers)
A random generator in a handful of lines: fast, evenly spread and reproducible at any time.
- Time per number
- O(1)
- State
- 64 Bit
- Output
- 32 Bit
- Cryptographically secure
- no
01What it is about
A computer does not roll dice. It calculates the next number from a single number, the state, and if the result looks evenly spread and hard to predict, we call it random.
PCG (Permuted Congruential Generator) is such a method. It works with 64 bits of state, is extremely fast and still produces numbers that are distributed far better than those of the classic simple generators.
The big advantage: the same starting value always produces the same sequence. For games, simulations or procedurally generated worlds that is exactly what you want.
02How it works
PCG consists of two parts.
The state is multiplied by a fixed number and increased by another fixed number on every call. On its own that is a linear congruential generator. It is fast, but its lower bits are noticeably regular.
The output function rescues the result. It scrambles the state by combining it with a shifted copy of itself using XOR, takes the upper 32 bits of that and rotates them. How far it rotates is decided by the topmost five bits of the state, so it changes on every call. It is exactly this varying rotation that makes the patterns disappear.
03Try it
04Implementation
public sealed class Pcg
{
// Constants taken from the reference implementation (PCG-XSH-RR, 32 bit output).
private const ulong Multiplier = 6364136223846793005;
private const ulong Increment = 1442695040888963407;
private ulong _state;
public Pcg(ulong seed)
{
_state = seed + Increment;
NextUInt(); // one warm up step mixes the seed into the state
}
// Advances the state and folds it down into a well distributed 32 bit number.
public uint NextUInt()
{
var state = _state;
// The state itself is a plain linear congruential generator: fast, but on its own
// it produces visible patterns. The quality comes from the output function below.
_state = state * Multiplier + Increment;
// The upper 5 bits decide how far the result is rotated. Because that amount
// changes with every step, the patterns of the generator disappear.
var rotation = (int)(state >> 59);
var folded = (uint)((state ^ (state >> 18)) >> 27);
return RotateRight(folded, rotation);
}
// Whole number in the range [0, exclusiveMaximum).
public int Next(int exclusiveMaximum) => (int)(NextUInt() % (uint)exclusiveMaximum);
// Floating point number in the range [0, 1). 4294967296 is 2^32, one more than uint.MaxValue.
public double NextDouble() => NextUInt() / 4294967296.0;
// Shifts all bits to the right; the bits falling off re-enter on the left.
private static uint RotateRight(uint value, int amount) => value >> amount | value << (32 - amount);
}05Example
// The same seed always produces the same sequence of numbers.
var random = new Pcg(seed: 42);
Console.WriteLine(random.NextUInt());
Console.WriteLine(random.Next(exclusiveMaximum: 6) + 1); // a dice roll
Console.WriteLine(random.NextDouble());
// Ten thousand values, counted into ten buckets - they spread out evenly.
var buckets = new int[10];
for (var i = 0; i < 10_000; i++)
buckets[random.Next(10)]++;
Console.WriteLine(string.Join(" ", buckets));3270867926
6
0.4481155041139573
975 956 1027 982 1036 971 1004 1014 993 104206Good to know
- Reproducibility is the real value here: with the same seed a bug in a simulation can be reproduced exactly.
- PCG is not suitable for security purposes. Passwords, tokens and keys belong to
System.Security.Cryptography.RandomNumberGenerator. random.Next(6)uses a plain modulo here. With very large upper bounds that makes the smallest values slightly more likely. If that matters, discard the few outliers and draw again.