C++ uniform_int_distribution gibt immer min() beim ersten Aufruf zurück

Question

In mindestens einer Implementierung der Standardbibliothek gibt der erste Aufruf einer std::uniform_int_distribution<>nicht einen Zufallswert zurück, sondern den minimalen Wert der Verteilung. Das heißt, der Code gegeben:

default_random_engine engine(any_seed()); 
uniform_int_distribution<int> distribution(smaller, larger); 
auto x = distribution(engine); 
assert(x == smaller); 

... x wird in der Tat smaller für beliebige Werte von any_seed(), smaller oder larger.

Um zu Hause zu spielen, können Sie versuchen, eine code sample, die dieses Problem in gcc 4.8.1 zeigt.

Ich vertraue darauf ist nicht richtiges Verhalten? Wenn es richtiges Verhalten ist, warum würde eine zufällige Verteilung diesen eindeutig nicht zufälligen Wert zurückgeben?

Answer 1

Erklärung für das beobachtete Verhalten

Dies ist, wie uniform_int_distribution die Zufallsbits auf Zahlen abbildet, wenn die Bandbreite möglicher Ergebnisse ist kleiner als der Bereich der Anzahl der RNG erzeugt:

const __uctype __uerange = __urange + 1; // __urange can be zero 
const __uctype __scaling = __urngrange/__uerange; 
const __uctype __past = __uerange * __scaling; 
do 
    __ret = __uctype(__urng()) - __urngmin; 
while (__ret >= __past); 
__ret /= __scaling; 

wo __urange ist larger - smaller und __urngrange ist die Differenz zwischen dem maximalen und dem minimalen Wert, die der Rng zurückgeben kann. (Code aus Bits/uniform_int_dist.h in libstdC++ 6.1)

In unserem Fall RNG default_random_engine ist ein minstd_rand0, die __scaling == 195225785 für den Bereich ergibt [0,10] Sie getestet. Wenn also rng() < 195225785, wird die Verteilung zurück 0.

Die erste Zahl, die eine minstd_rand0 kehrt ist

(16807 * seed) % 2147483647 

(wo seed == 0 btw zu 1 eingestellt wird). Wir können also sehen, dass der erste Wert, der von einem minstd_rand0 mit einer kleineren Nummer als 11615 ausgesät wird, 0 mit dem von Ihnen verwendeten uniform_int_distribution<int> distribution(0, 10); ergibt. (mod off-by-one-errors meinerseits.;))

Du erwähntest das Problem weggehen für größere Samen: Sobald die Samen groß genug werden, um die Mod-Operation tatsächlich etwas zu tun, können wir nicht einfach Weisen Sie der gleichen Ausgabe durch Division einen ganzen Bereich von Werten zu, damit die Ergebnisse besser aussehen.

Bedeutet das (libstdC++ 's impl) < zufällig > ist kaputt?

Nein. Sie haben eine signifikante Verzerrung in einem zufälligen 32-Bit-Seed eingeführt, indem Sie es immer klein gewählt haben. Diese Voreingenommenheit, die sich in den Ergebnissen zeigt, ist nicht überraschend oder böse. Für zufällige Seeds wird sogar Ihr minstd_rand0 einen ziemlich gleichmäßigen ersten Zufallswert liefern. (Obwohl die Folge von Zahlen danach nicht von großer statistischer Qualität sein wird.)

Was können wir dagegen tun?

Fall 1: Sie wollen Zufallszahl hoher statistischer Qualität.

Dafür verwenden Sie eine bessere Rng wie mt19937 und Seed gesamten State Space. Für den Mersenne Twister sind das 624 32-Bit-Ganzzahlen. (Als Referenz ist here mein Versuch, dies mit einem paar hilfreichen Anregungen in der Antwort richtig zu tun.)

Fall 2: Sie wollen wirklich nur die kleinen Samen verwenden.

Wir können immer noch anständige Ergebnisse daraus erhalten. Das Problem ist, dass Pseudozufallszahlengeneratoren gewöhnlich "etwas kontinuierlich" von ihrem Seed abhängen. Um dies zu umgehen, verwerfen wir genügend Zahlen, um die anfangs ähnlichen Folgen der Ausgabe divergieren zu lassen. Also, wenn Ihr Samen klein sein müssen, können Sie Ihre RNG wie folgt initialisieren:

std::mt19937 rng(smallSeed); 
rng.discard(700000); 

Es ist wichtig, dass Sie eine gute RNG wie der Mersenne-Twister für diese. Ich kenne keine Methode, um selbst anständige Werte aus einem schlecht gesetzten minstd_rand0 zu erhalten, zum Beispiel siehe this train-wreck. Selbst bei richtiger Aussaat sind die statistischen Eigenschaften eines mt19937 bei weitem überlegen.

Bedenken über den großen Zustandsraum oder die langsame Generation, von denen man manchmal hört, sind normalerweise außerhalb der eingebetteten Welt nicht von Belang. Nach boost und cacert.at ist das MT sogar viel schneller als minstd_rand0.

Sie müssen immer noch den Abwurf Trick tun, auch wenn Ihre Ergebnisse mit dem bloßen Auge ohne gut aussehen. Es dauert weniger als eine Millisekunde auf meinem System, und Sie nicht sehr häufig Seeds, so gibt es keinen Grund nicht zu.

Beachten Sie, dass ich nicht in der Lage bin, Ihnen eine scharfe Schätzung für die Anzahl der Rückwürfe zu geben, die wir brauchen, nahm ich diesen Wert von this answer, verbindet es this paper für eine rationale. Ich habe jetzt nicht die Zeit, das durchzuarbeiten.