Zufall & RauschenRND-01
PCG (Zufallszahlen)
Ein Zufallsgenerator aus wenigen Zeilen: schnell, gleichmäßig und jederzeit reproduzierbar.
- Laufzeit pro Zahl
- O(1)
- Zustand
- 64 Bit
- Ausgabe
- 32 Bit
- Kryptografisch sicher
- nein
01Worum es geht
Ein Computer würfelt nicht. Er rechnet aus einer Zahl, dem Zustand, die nächste aus, und wenn das Ergebnis gleichmäßig gestreut und schwer vorhersagbar aussieht, nennt man es Zufall.
PCG (Permuted Congruential Generator) ist so ein Verfahren. Es kommt mit 64 Bit Zustand aus, ist extrem schnell und liefert trotzdem Zahlen, die deutlich besser verteilt sind als bei den klassischen einfachen Generatoren.
Der große Vorteil: Derselbe Startwert liefert immer dieselbe Zahlenfolge. Für Spiele, Simulationen oder prozedural erzeugte Welten ist das genau das, was man will.
02So funktioniert es
PCG besteht aus zwei Teilen.
Der Zustand wird bei jedem Aufruf mit einer festen Zahl multipliziert und um eine feste Zahl erhöht. Das allein ist ein linearer Kongruenzgenerator. Er ist schnell, aber seine unteren Bits sind auffällig regelmäßig.
Die Ausgabefunktion rettet das Ergebnis. Sie verwürfelt den Zustand, indem sie ihn mit einer verschobenen Kopie seiner selbst per XOR verknüpft, nimmt daraus die oberen 32 Bit und rotiert sie. Wie weit rotiert wird, bestimmen die obersten fünf Bits des Zustands, also ändert sich das bei jedem Aufruf. Genau diese variable Rotation lässt die Muster verschwinden.
03Ausprobieren
04Implementierung
public sealed class Pcg
{
// Konstanten aus der Referenzimplementierung (PCG-XSH-RR, 32 Bit Ausgabe).
private const ulong Multiplier = 6364136223846793005;
private const ulong Increment = 1442695040888963407;
private ulong _state;
public Pcg(ulong seed)
{
_state = seed + Increment;
NextUInt(); // ein Aufwärmschritt mischt den Startwert in den Zustand
}
// Rückt den Zustand weiter und faltet ihn zu einer gut verteilten 32-Bit-Zahl.
public uint NextUInt()
{
var state = _state;
// Der Zustand allein ist ein linearer Kongruenzgenerator: schnell, aber für sich
// erzeugt er sichtbare Muster. Die Qualität kommt von der Ausgabefunktion unten.
_state = state * Multiplier + Increment;
// Die oberen 5 Bits bestimmen, wie weit rotiert wird. Weil sich dieser Wert
// bei jedem Schritt ändert, verschwinden die Muster des Generators.
var rotation = (int)(state >> 59);
var folded = (uint)((state ^ (state >> 18)) >> 27);
return RotateRight(folded, rotation);
}
// Ganze Zahl im Bereich [0, exclusiveMaximum).
public int Next(int exclusiveMaximum) => (int)(NextUInt() % (uint)exclusiveMaximum);
// Kommazahl im Bereich [0, 1). 4294967296 ist 2^32, eins mehr als uint.MaxValue.
public double NextDouble() => NextUInt() / 4294967296.0;
// Schiebt alle Bits nach rechts; die herausfallenden Bits kommen links wieder herein.
private static uint RotateRight(uint value, int amount) => value >> amount | value << (32 - amount);
}05Beispiel
// Derselbe Startwert liefert immer dieselbe Zahlenfolge.
var random = new Pcg(seed: 42);
Console.WriteLine(random.NextUInt());
Console.WriteLine(random.Next(exclusiveMaximum: 6) + 1); // ein Würfelwurf
Console.WriteLine(random.NextDouble());
// Zehntausend Werte, gezählt in zehn Fächern - sie verteilen sich gleichmäßig.
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 104206Gut zu wissen
- Reproduzierbarkeit ist der eigentliche Wert: Mit demselben Seed lässt sich ein Fehler in einer Simulation exakt nachstellen.
- Für Sicherheitszwecke ist PCG nicht geeignet. Passwörter, Tokens und Schlüssel gehören zu
System.Security.Cryptography.RandomNumberGenerator. random.Next(6)benutzt hier ein einfaches Modulo. Bei sehr großen Obergrenzen sind dadurch die kleinsten Werte minimal wahrscheinlicher. Wen das stört, der verwirft die wenigen Ausreißer und zieht neu.