Was ist die richtige Methode, um eine Pseudozufallszahl auf einen kleineren Bereich zu beschränken?

Question

Was ist der beste Weg, um die Werte eines PRNG auf einen kleineren Bereich zu beschränken? Wenn Sie den Modulus verwenden und die alte maximale Zahl nicht durch die neue maximale Zahl teilbar ist, dann richten Sie sich auf die 0 bis (old_max - new_max - 1). Ich nehme an, der beste Weg wäre in etwa so sein (dies ist Gleitkomma, nicht integer math)

random_num = PRNG()/max_orginal_range * max_smaller_range 

aber etwas in meinem Bauch macht mich diese Methode in Frage (vielleicht Punkt Umsetzung und Darstellung Unterschiede Floating?).

Der Zufallszahlengenerator wird konsistente Ergebnisse über die Hardware- und Softwareplattformen hinweg liefern, und die Einschränkung muss auch.

Ich hatte Recht, den Pseudocode oben zu bezweifeln (aber nicht aus den Gründen, die ich dachte). MichaelGGs answer hat mich auf andere Weise über das Problem nachdenken lassen. Ich kann es mit kleineren Zahlen modellieren und jedes Ergebnis testen. Nehmen wir an, wir haben einen PRNG, der eine Zufallszahl zwischen 0 und 31 erzeugt, und Sie möchten, dass der kleinere Bereich zwischen 0 und 9 liegt. Wenn Sie modul verwenden, orientieren Sie sich an 0, 1, 2 und 3. Wenn Sie den Pseudocode verwenden über Ihnen neigen Sie in Richtung 0, 2, 5 und 7. Ich denke nicht, dass es einen guten Weg geben kann, einen Satz in den anderen zu kartieren. Das Beste, was ich bisher herausgefunden habe, ist, die Zufallszahlen zu regenerieren, die größer sind als old_max/new_max, aber das hat auch tiefe Probleme (die Periode reduzieren, Zeit, um neue Zahlen zu erzeugen, bis einer im richtigen Bereich ist, etc.) .

Ich denke, ich habe naiv dieses Problem angegangen. Es könnte an der Zeit sein, ernsthafte Forschung in der Literatur zu beginnen (jemand muss das schon einmal angepackt haben).

Answer 1

Ich weiß, dass dies keine besonders hilfreiche Antwort sein könnte, aber ich denke, der beste Weg wäre, sich ein paar verschiedene Methoden vorzustellen, sie dann ein paar Millionen Mal auszuprobieren und die Ergebnissätze zu überprüfen.

Im Zweifelsfall versuchen Sie es selbst.

EDIT

Es sollte beachtet werden, dass viele Sprachen (wie C#) in ihren Funktionen aufgebaut haben

bei der Begrenzung

int maximumvalue = 20; 
Random rand = new Random(); 

rand.Next(maximumvalue); 

Und wann immer möglich, sollten Sie diejenigen, anstatt jeden Code verwenden würden Sie schreib dich. Erfinde das Rad nicht neu.

Answer 2

Wenn PRNG() gleichverteilte Zufallszahlen erzeugt, dann sieht das obige gut aus. In der Tat (wenn Sie den Mittelwert usw. skalieren wollen), sollte das oben für alle Zwecke gut sein. Ich denke, Sie müssen fragen, was der Fehler im Zusammenhang mit der ursprünglichen PRNG() ist, und ob weitere Manipulation wesentlich dazu beitragen wird.

Im Zweifelsfall erzeugen ein entsprechend dimensioniertes Probensatz, und schauen Sie sich die Ergebnisse in Excel oder ähnlich (lesen Mittelwert/std.dev usw. für das, was man erwarten würde)

Answer 3

Wenn Sie Zugriff haben zu einer PRNG-Funktion (etwa random()), dass im Bereich 0 erzeugen Zahlen werden < = x < 1, kann man nicht einfach tun:

random_num = (int) (random() * max_range); 

Ihnen Zahlen im Bereich geben 0 bis max_range?

Answer 4

Hier ist, wie die Zufallsklasse CLR funktioniert, wenn begrenzt (per Reflector):

long num = maxValue - minValue; 
if (num <= 0x7fffffffL) { 
    return (((int) (this.Sample() * num)) + minValue); 
} 
return (((int) ((long) (this.GetSampleForLargeRange() * num))) + minValue); 

Selbst wenn Sie eine positive int gegeben sind, ist es nicht schwer, es zu einem Doppel zu bekommen. Multiplizieren Sie einfach das zufällige int mit (1/maxint). Der Übergang von einem 32-Bit-Int zu einem Double sollte ausreichende Genauigkeit bieten. (Ich habe einen PRNG nicht wirklich so geprüft, also könnte ich etwas mit Hin- und Herbewegungen vermissen.)

Answer 5

Pseudozufallszahlgeneratoren produzieren im Wesentlichen eine gelegentliche Reihe von 1s und 0s, die, wenn sie an einander angebracht werden, ein sind unendlich große Zahl in der Basis zwei. Jedes Mal, wenn du etwas von dir verbrauchst, dividierst du diese Zahl durch zwei und hältst den Modulus. Sie können dies für immer tun, ohne ein einziges Bit zu verschwenden.

Wenn Sie eine Zahl im Bereich [0, N] benötigen, dann brauchen Sie das Gleiche, aber statt der zweiten benötigen Sie die Basis N. Es ist im Grunde trivial, die Basen zu konvertieren. Verbrauchen Sie die Anzahl der Bits, die Sie benötigen, und geben Sie den Rest dieser Bits zurück an Ihr prng, um das nächste Mal verwendet zu werden, wenn eine Nummer benötigt wird.