Zufallszahlen in C ++

12

Kürzlich habe ich mich an moderne Sprachen gewöhnt, zu denen ein guter Zufallsgenerator gehört, normalerweise der Mersenne Twister. Nachdem ich wieder zu C ++ zurückgekehrt bin, muss ich entscheiden, was ich verwenden möchte.

Ich habe nach Mersenne Twister-Implementierungen gesucht und festgestellt, dass es so viele gibt: Gibt es eine, die häufiger verwendet und verbreitet wird, oder soll ich eine auswählen, wenn sie alle gleich gut sind?

o0 '.
quelle
1
Ich mag Ihre Trennung von C ++ und modernen Sprachen.
Jcora
2
Vielleicht war es angemessener, "höheres Niveau" zu sagen.
o0 '.
Ich denke, diese Frage gehört auf Stackoverflow
TravisG
5
Auf SO würde ich eine andere Antwort geben, weil ich nicht wüsste, dass es sich um eine Game-Engine handelt, im Gegensatz zu Monte-Carlo-Simulationen für medizinische Therapien. In diesem Fall kann es tödlich sein, keine 624 Dimensionen von Zufälligkeit zu haben.

Antworten:

19

C ++ 11 enthält standardmäßig einen Mersenne Twister-Generator als Teil seiner neuen <random>Schnittstelle. Um beispielsweise mit MT ganze Zahlen gleichmäßig zwischen [-10, 10] zu generieren, gehen Sie wie folgt vor:

std::mt19937 eng; // This is the Mersenne Twister
std:::uniform_int_distribution<int> dist(-10, 10)
for (int i = 0; i < 10; ++i)
    std::cout << dist(eng) << std::endl;

Das meiste davon ist auch in jedem Compiler verfügbar, der TR1 anbietet, obwohl die Namen leicht unterschiedlich sind. std::tr1::mt19937und std::tr1::uniform_int<int>.

Normalerweise warne ich Leute davor, Mersenne Twister zu benutzen. Es ist ein akzeptabler Algorithmus, aber ein Großteil seiner Popularität ist nur Marketing. 624 Dimensionen der Zufälligkeit sind mehr als die meisten Menschen brauchen, und MT stellt relativ hohe Zustandsanforderungen, und wenn es eine vollständige Tabellenumrechnung durchführt, kann es den Cache sprengen. Ich persönlich bin ein Teil von xorshift, das exzellente Perioden und angemessene Verteilungen für alles bietet, was ein Spiel benötigt, mit winzigen Speicher- und CPU-Anforderungen.

Ich habe einen (meistens?) C ++ 11-kompatiblen Xorshift-Generator geschrieben - xorshift.hpp , xorshift.cpp - und ihn öffentlich zugänglich gemacht. Sie können dies in eine beliebige C ++ 11-Randomisierungsfunktion wie oben einbinden:

xorshift eng;
std:::uniform_int_distribution<int> dist(-10, 10)
for (int i = 0; i < 10; ++i)
    std::cout << dist(eng) << std::endl;

quelle
5
Ja, das ist die Art von Antwort, nach der ich gesucht habe, deshalb habe ich hier auf gamedev gepostet:)
o0 '.
1
Ich wollte nur darauf hinweisen, dass nichts in den Dateien, die Sie verlinkt haben, darauf hindeutet, dass sie gemeinfrei sind. Die Art und Weise, wie das Urheberrecht funktioniert, muss unbedingt klargestellt werden, da das Gesetz standardmäßig "alle Rechte vorbehalten" voraussetzt. Es ist sogar noch sicherer, nur so etwas wie die MIT- oder BSD-2-Klausel-Lizenz zu verwenden, da einige Gerichtsbarkeiten "dies ist gemeinfrei" grundsätzlich nicht als rechtlich bindend anerkennen. Wenn Sie daran interessiert sind, zu sehen, wie Leute Ihren Code verwenden, kann es sich lohnen, sich darum zu kümmern.
Sean Middleditch
1
@seanmiddleditch: Ich bin mir darüber im Klaren. Wenn Sie es unter einer MIT-artigen Lizenz wünschen, folge ich dem Beispiel von SQLite und gebe es Ihnen für nur 1000 USD.
Das Hauptproblem ist das Fehlen eines Headers im Code, der etwas deklariert (was SQLite macht, iirc). Wenn es dich nicht interessiert, ist das cool. Ich habe Ihnen nur einen freundlichen Vorschlag gemacht.
Sean Middleditch
1

Ein anderes RNG, das ich zuvor für Spielezwecke verwendet habe, ist Bob Jenkins "kleines" RNG, das hier beschrieben wird .

(Er hat auch ein RNG mit kryptografischer Stärke namens ISAAC, aber es ist größer und langsamer, und Spiele benötigen diese Stärke nicht.)

Nathan Reed
quelle
1
Das sieht teurer aus als Xorshift (4 Xors und 3 Shifts vs. 4 Adds, 6 Shifts, 2 Ors und ein Xor), hat einen schlechteren Zeitraum und läuft bei bestimmten Initialisierungen Gefahr, sehr kurze Zyklen zu durchlaufen. Es sieht schnell aber nicht am schnellsten aus; okay, aber bei weitem nicht optimal; gleiche Grundverteilungsqualitäten wie Xorshift; Ich sehe keinen Grund, es zu benutzen.
Meinetwegen. Ich weiß nicht genug über die RNG-Analyse, um die Verteilungs- und Zykluseigenschaften zu untersuchen.
Nathan Reed