Schreiben Sie bei einer gegebenen Funktion, die eine zufällige Ganzzahl im Bereich von 1 bis 5 erzeugt, eine Funktion, die eine zufällige Ganzzahl im Bereich von 1 bis 7 erzeugt.
- Was ist eine einfache Lösung?
- Was ist eine effektive Lösung, um die Speichernutzung zu reduzieren oder auf einer langsameren CPU zu laufen?
7 * rand5() / 5
?Antworten:
Dies entspricht der Lösung von Adam Rosenfield, ist jedoch für einige Leser möglicherweise etwas klarer. Es wird davon ausgegangen, dass rand5 () eine Funktion ist, die eine statistisch zufällige Ganzzahl im Bereich von 1 bis einschließlich 5 zurückgibt.
Wie funktioniert es? Stellen Sie sich das so vor: Stellen Sie sich vor, Sie drucken dieses zweidimensionale Array auf Papier aus, heften es an eine Dartscheibe und werfen zufällig Pfeile darauf. Wenn Sie einen Wert ungleich Null treffen, ist dies ein statistisch zufälliger Wert zwischen 1 und 7, da eine gleiche Anzahl von Werten ungleich Null zur Auswahl steht. Wenn Sie eine Null treffen, werfen Sie den Pfeil einfach weiter, bis Sie eine Nicht-Null treffen. Genau das macht dieser Code: Die Indizes i und j wählen zufällig einen Ort auf der Dartscheibe aus, und wenn wir kein gutes Ergebnis erzielen, werfen wir weiter Darts.
Wie Adam sagte, kann dies im schlimmsten Fall für immer laufen, aber statistisch gesehen passiert der schlimmste Fall nie. :) :)
quelle
rand5
es einheitlich ist, hat jede Zelle imvals
Raster die gleiche Wahrscheinlichkeit, ausgewählt zu werden. Das Raster enthält genau drei Kopien jeder Ganzzahl im Intervall [1, 7] sowie vier Nullen. Der "rohe" Ergebnisstrom tendiert also zu einer gleichmäßigen Mischung von [1, 7] -Werten plus einigen Nullen, die etwas häufiger auftreten als jeder einzelne zulässige Wert. Dies spielt jedoch keine Rolle, da die Nullen entfernt werden und nur eine gleichmäßige Mischung von [1, 7] -Werten übrig bleibt.Es gibt keine (genau korrekte) Lösung, die in einer konstanten Zeitspanne ausgeführt wird, da 1/7 eine unendliche Dezimalstelle in Basis 5 ist. Eine einfache Lösung wäre die Verwendung der Ablehnungsabtastung, z.
Dies hat eine erwartete Laufzeit von 25/21 = 1,19 Iterationen der Schleife, aber es gibt eine unendlich geringe Wahrscheinlichkeit, dass die Schleife für immer wiederholt wird.
quelle
N
undrand5()
im schlimmsten Fall garantiert nur Anrufe tätigt . Dann gibt es 5 ^ N mögliche Ergebnisse der Folge von Anrufen anrand5
, von denen jeder eine Ausgabe von 1-7 hat. Wenn Sie also alle möglichen Folgen von Anrufenk
addieren, deren Ausgabe für jeweils 1 ≤ k ≤ 7 ist, beträgt die Wahrscheinlichkeit, dass die Ausgabek
m / 5 ^ N ist, wobei m die Anzahl solcher Folgen ist. Also, m / 5 ^ N = 1/7, aber es gibt keine möglichen ganzzahligen Lösungen (N, m) für diesen ==> Widerspruch.Ich möchte zusätzlich zu meiner ersten Antwort eine weitere Antwort hinzufügen . Diese Antwort versucht, die Anzahl der Anrufe
rand5()
pro Anruf zu minimierenrand7()
, um die Verwendung der Zufälligkeit zu maximieren. Das heißt, wenn Sie Zufälligkeit als wertvolle Ressource betrachten, möchten wir so viel wie möglich davon verwenden, ohne zufällige Teile wegzuwerfen. Diese Antwort hat auch einige Ähnlichkeiten mit der in Iwans Antwort dargestellten Logik .Die Entropie einer Zufallsvariablen ist eine genau definierte Größe. Für eine Zufallsvariable, die N Zustände mit gleichen Wahrscheinlichkeiten annimmt (eine gleichmäßige Verteilung), beträgt die Entropie log 2 N. Somit
rand5()
hat sie ungefähr 2,32193 Entropiebits undrand7()
ungefähr 2,80735 Entropiebits. Wenn wir die Zufälligkeit optimal nutzen möchten, müssen wir alle 2,32193 Entropiebits von jedem Aufruf an verwendenrand5()
und sie auf die Erzeugung von 2,80735 Entropiebits anwenden, die für jeden Aufruf von erforderlich sindrand7()
. Die grundlegende Grenze ist also, dass wir nicht besser als log (7) / log (5) = 1.20906 Anruferand5()
pro Anruf an machen könnenrand7()
.Randnotizen: Alle Logarithmen in dieser Antwort sind Basis 2, sofern nicht anders angegeben.
rand5()
Es wird angenommen, dass Zahlen im Bereich [0, 4] zurückgegeben werden, und esrand7()
wird angenommen, dass Zahlen im Bereich [0, 6] zurückgegeben werden. Das Anpassen der Bereiche auf [1, 5] bzw. [1, 7] ist trivial.Wie machen wir das? Wir erzeugen eine unendlich genaue reelle Zufallszahl zwischen 0 und 1 (tun Sie so, als könnten wir tatsächlich eine so unendlich genaue Zahl berechnen und speichern - wir werden dies später beheben). Wir können eine solche Zahl erzeugen, indem wir ihre Ziffern in Basis 5 erzeugen: Wir wählen die Zufallszahl 0.
a
1a
2a
3 ..., wobei jede Ziffer ai
durch einen Aufruf von ausgewählt wirdrand5()
. Wenn unser RNG beispielsweise ai
= 1 für alle gewählti
hat und die Tatsache ignoriert, dass dies nicht sehr zufällig ist, würde dies der reellen Zahl 1/5 + 1/5 2 + 1/5 3 + ... = entsprechen 1/4 (Summe einer geometrischen Reihe).Ok, wir haben also eine zufällige reelle Zahl zwischen 0 und 1 ausgewählt. Ich behaupte jetzt, dass eine solche zufällige Zahl gleichmäßig verteilt ist. Intuitiv ist dies leicht zu verstehen, da jede Ziffer einheitlich ausgewählt wurde und die Zahl unendlich genau ist. Ein formaler Beweis dafür ist jedoch etwas komplizierter, da es sich jetzt um eine kontinuierliche Verteilung anstelle einer diskreten Verteilung handelt. Daher müssen wir beweisen, dass die Wahrscheinlichkeit, dass unsere Zahl in einem Intervall [
a
,b
] liegt, gleich der Länge von ist dieses Intervall ,b - a
. Der Beweis bleibt als Übung für den Leser =).Nachdem wir nun eine zufällige reelle Zahl einheitlich aus dem Bereich [0, 1] ausgewählt haben, müssen wir sie in eine Reihe einheitlich zufälliger Zahlen im Bereich [0, 6] umwandeln, um die Ausgabe von zu generieren
rand7()
. Wie machen wir das? Genau das Gegenteil von dem, was wir gerade getan haben - wir konvertieren es in eine unendlich genaue Dezimalstelle in Basis 7, und dann entspricht jede Ziffer von Basis 7 einer Ausgabe vonrand7()
.Wenn wir im Beispiel von früher
rand5()
einen unendlichen Strom von Einsen erzeugen, ist unsere zufällige reelle Zahl 1/4. Wenn wir 1/4 in Basis 7 konvertieren, erhalten wir die unendliche Dezimalzahl 0,15151515 ..., sodass wir als Ausgabe 1, 5, 1, 5, 1, 5 usw. erzeugen.Ok, wir haben also die Hauptidee, aber wir haben noch zwei Probleme: Wir können keine unendlich genaue reelle Zahl berechnen oder speichern. Wie gehen wir also mit nur einem endlichen Teil davon um? Zweitens, wie konvertieren wir es tatsächlich in Basis 7?
Eine Möglichkeit, eine Zahl zwischen 0 und 1 in Basis 7 umzuwandeln, ist folgende:
Um das Problem der unendlichen Genauigkeit zu lösen, berechnen wir ein Teilergebnis und speichern eine Obergrenze für das Ergebnis. Nehmen wir an, wir haben
rand5()
zweimal angerufen und es wurde beide Male 1 zurückgegeben. Die Zahl, die wir bisher generiert haben, ist 0,11 (Basis 5). Was auch immer der Rest der unendlichen Reihe von Aufrufen seinrand5()
mag, die zufällige reelle Zahl, die wir erzeugen, wird niemals größer als 0,12 sein: Es ist immer wahr, dass 0,11 ≤ 0,11xyz ... <0,12.Wenn wir also die aktuelle Zahl und den Maximalwert verfolgen, den es jemals annehmen könnte, konvertieren wir beide Zahlen in Basis 7. Wenn sie sich auf die ersten
k
Ziffern einigen , können wir die nächstenk
Ziffern sicher ausgeben - unabhängig davon, welche Unendlicher Strom von Basis 5-Ziffern, sie werden niemals die nächstenk
Ziffern der Basis 7-Darstellung beeinflussen!Und das ist der Algorithmus - um die nächste Ausgabe von zu generieren
rand7()
, generieren wir nur so viele Ziffern,rand5()
wie wir benötigen, um sicherzustellen, dass wir den Wert der nächsten Ziffer bei der Konvertierung der reellen Zufallszahl in Basis 7 mit Sicherheit kennen eine Python-Implementierung mit einem Testgeschirr:Beachten Sie, dass
rand7_gen()
ein Generator zurückgegeben wird, da er einen internen Status hat, der die Konvertierung der Zahl in Basis 7 beinhaltet. Das Testkabel ruftnext(r7)
10000 Mal auf, um 10000 Zufallszahlen zu erzeugen, und misst dann deren Verteilung. Es wird nur eine ganzzahlige Mathematik verwendet, sodass die Ergebnisse genau korrekt sind.Beachten Sie auch, dass die Zahlen hier sehr groß werden, sehr schnell. Potenzen von 5 und 7 wachsen schnell. Daher wird sich die Leistung nach der Erzeugung vieler Zufallszahlen aufgrund der Bignum-Arithmetik merklich verschlechtern. Aber denken Sie daran, mein Ziel war es, die Verwendung von Zufallsbits zu maximieren, nicht die Leistung zu maximieren (obwohl dies ein sekundäres Ziel ist).
In einem Durchgang habe ich 12091 Anrufe
rand5()
für 10000 Anrufe getätigtrand7()
, wobei das Minimum von log (7) / log (5) -Aufrufen im Durchschnitt auf 4 signifikante Zahlen erreicht wurde, und die resultierende Ausgabe war einheitlich.Um diesen Code in eine Sprache zu portieren, in der keine beliebig großen Ganzzahlen integriert sind, müssen Sie die Werte
pow5
undpow7
den Maximalwert Ihres nativen Integraltyps begrenzen. Wenn diese zu groß werden, setzen Sie sie zurück alles und von vorne anfangen. Dadurch wird die durchschnittliche Anzahl der Anruferand5()
pro Anrufrand7()
geringfügig erhöht, aber hoffentlich sollte sie auch bei 32- oder 64-Bit-Ganzzahlen nicht zu stark ansteigen.quelle
(Ich habe die Antwort von Adam Rosenfeld gestohlen und sie um etwa 7% schneller laufen lassen.)
Angenommen, rand5 () gibt eines von {0,1,2,3,4} mit gleicher Verteilung zurück und das Ziel ist die Rückgabe von {0,1,2,3,4,5,6} mit gleicher Verteilung.
Wir verfolgen den größten Wert, den die Schleife in der Variablen erzeugen kann
max
. Wenn das bisherige Ergebnis zwischen max% 7 und max-1 liegt, wird das Ergebnis in diesem Bereich gleichmäßig verteilt. Wenn nicht, verwenden wir den Rest, der zufällig zwischen 0 und max% 7-1 liegt, und einen weiteren Aufruf von rand (), um eine neue Nummer und eine neue max. Dann fangen wir wieder an.Bearbeiten: Erwarten Sie, wie oft rand5 () aufgerufen wird, ist x in dieser Gleichung:
quelle
5 * rand5() + rand5()
.Algorithmus:
7 kann in einer Folge von 3 Bits dargestellt werden
Verwenden Sie rand (5), um jedes Bit zufällig mit 0 oder 1 zu füllen.
Zum Beispiel: Rufen Sie rand (5) und auf
Wenn das Ergebnis 1 oder 2 ist, füllen Sie das Bit mit 0,
wenn das Ergebnis 4 oder 5 ist, füllen Sie das Bit mit 1,
wenn das Ergebnis 3 ist, ignorieren Sie es und wiederholen Sie es (Zurückweisung)
Auf diese Weise können wir 3 Bits zufällig mit 0/1 füllen und so eine Zahl von 1-7 erhalten.
EDIT: Dies scheint die einfachste und effizienteste Antwort zu sein. Hier ist ein Code dafür:
quelle
quelle
Edit: Das funktioniert nicht ganz. Es ist um ungefähr 2 Teile in 1000 (unter der Annahme eines perfekten Rand5). Die Eimer bekommen:
Durch Umschalten auf eine Summe von
scheint für jede 2 hinzugefügten eine Größenordnung zu gewinnen
Übrigens: Die obige Fehlertabelle wurde nicht durch Stichproben generiert, sondern durch die folgende Wiederholungsrelation:
quelle
quelle
ans += (r < 3) << i
Das Folgende erzeugt eine gleichmäßige Verteilung auf {1, 2, 3, 4, 5, 6, 7} unter Verwendung eines Zufallszahlengenerators, der eine gleichmäßige Verteilung auf {1, 2, 3, 4, 5} erzeugt. Der Code ist chaotisch, aber die Logik ist klar.
quelle
Im Gegensatz zur gewählten Lösung wird der Algorithmus in konstanter Zeit ausgeführt. Rand5 wird jedoch 2 Mal mehr aufgerufen als die durchschnittliche Laufzeit der ausgewählten Lösung.
Beachten Sie, dass dieser Generator nicht perfekt ist (die Zahl 0 hat eine um 0,0064% höhere Wahrscheinlichkeit als jede andere Zahl), aber für die meisten praktischen Zwecke überwiegt die Garantie einer konstanten Zeit wahrscheinlich diese Ungenauigkeit.
Erläuterung
Diese Lösung ergibt sich aus der Tatsache, dass die Zahl 15.624 durch 7 teilbar ist. Wenn wir also zufällig und gleichmäßig Zahlen von 0 bis 15.624 erzeugen und dann Mod 7 nehmen können, können wir einen nahezu einheitlichen rand7-Generator erhalten. Zahlen von 0 bis 15.624 können einheitlich erzeugt werden, indem rand5 sechsmal gewürfelt und daraus die Ziffern einer Basis-5-Zahl wie folgt gebildet werden:
Die Eigenschaften von Mod 7 erlauben es uns jedoch, die Gleichung ein wenig zu vereinfachen:
Damit
wird
Theorie
Die Zahl 15.624 wurde nicht zufällig ausgewählt, sondern kann mit dem kleinen Satz von Fermat entdeckt werden, der besagt, dass wenn p eine Primzahl ist, dann
Das gibt uns also,
(5 ^ 6) -1 ist gleich
Dies ist eine Zahl in Basis 5-Form, und daher können wir sehen, dass diese Methode verwendet werden kann, um von einem beliebigen Zufallszahlengenerator zu einem anderen Zufallszahlengenerator zu wechseln. Bei Verwendung des Exponenten p-1 wird jedoch immer eine kleine Vorspannung in Richtung 0 eingeführt.
Um diesen Ansatz zu verallgemeinern und genauer zu sein, können wir eine Funktion wie diese haben:
quelle
Sind hier Hausaufgabenprobleme erlaubt?
Diese Funktion berechnet grob "Basis 5", um eine Zahl zwischen 0 und 6 zu generieren.
quelle
Wenn wir die zusätzliche Einschränkung betrachten, zu versuchen, die effizienteste Antwort zu geben, dh eine, die bei einem Eingabestream
I
von gleichmäßig verteilten Ganzzahlen mit einer Längem
von 1 bis 5 einen StromO
von gleichmäßig verteilten Ganzzahlen von 1 bis 7 der längsten relativen Länge ausgibt zum
sagenL(m)
.Der einfachste Weg, dies zu analysieren, besteht darin, die Ströme I und
O
als 5-ary- bzw. 7-ary-Zahlen zu behandeln. Dies wird durch die Idee der Hauptantwort erreicht, den Streama1, a2, a3,... -> a1+5*a2+5^2*a3+..
und ähnlich für den Stream zu nehmenO
.Dann nehmen wir einen Abschnitt des Eingabestreams mit der Länge,
m choose n s.t. 5^m-7^n=c
woc>0
und ist so klein wie möglich. Dann gibt es eine einheitliche Abbildung vom Eingabestrom der Länge m auf Ganzzahlen von1
bis5^m
und eine weitere einheitliche Abbildung von Ganzzahlen von 1 bis7^n
zum Ausgabestrom der Länge n, bei der wir möglicherweise einige Fälle aus dem Eingabestream verlieren müssen, wenn die Ganzzahl abgebildet wird überschreitet7^n
.Dies ergibt also einen Wert für
L(m)
ungefähr,m (log5/log7)
der ungefähr ist.82m
.Die Schwierigkeit bei der obigen Analyse ist die Gleichung,
5^m-7^n=c
die nicht einfach genau zu lösen ist, und der Fall, in dem der einheitliche Wert von1
bis5^m
übersteigt7^n
und wir an Effizienz verlieren.Die Frage ist, wie nahe der bestmögliche Wert von m (log5 / log7) erreicht werden kann. Wenn sich diese Zahl beispielsweise einer Ganzzahl nähert, können wir dann einen Weg finden, um diese exakte ganzzahlige Anzahl von Ausgabewerten zu erreichen?
Wenn
5^m-7^n=c
wir dann aus dem Eingabestream effektiv eine einheitliche Zufallszahl von0
bis generieren(5^m)-1
und keine höheren Werte als verwenden7^n
. Diese Werte können jedoch gerettet und erneut verwendet werden. Sie erzeugen effektiv eine einheitliche Folge von Zahlen von 1 bis5^m-7^n
. Wir können dann versuchen, diese zu verwenden und sie in 7-fache Zahlen umzuwandeln, damit wir mehr Ausgabewerte erstellen können.Wenn wir
T7(X)
die durchschnittliche Länge der Ausgabesequenz vonrandom(1-7)
ganzen Zahlen sein wollen, die aus einer einheitlichen Eingabe der Größe abgeleitet sindX
, und dies annehmen5^m=7^n0+7^n1+7^n2+...+7^nr+s, s<7
.Dann
T7(5^m)=n0x7^n0/5^m + ((5^m-7^n0)/5^m) T7(5^m-7^n0)
haben wir, da wir eine Länge haben, keine Folge mit der Wahrscheinlichkeit 7 ^ n0 / 5 ^ m mit einem Rest der Länge5^m-7^n0
mit der Wahrscheinlichkeit(5^m-7^n0)/5^m)
.Wenn wir einfach weiter ersetzen, erhalten wir:
Daher
Eine andere Art, dies auszudrücken, ist:
Der bestmögliche Fall ist mein Original oben wo
5^m=7^n+s
, wos<7
.Dann
T7(5^m) = nx(7^n)/(7^n+s) = n+o(1) = m (Log5/Log7)+o(1)
wie zuvor.Der schlimmste Fall ist, wenn wir nur k und st 5 ^ m = kx7 + s finden können.
Andere Fälle liegen irgendwo dazwischen. Es wäre interessant zu sehen, wie gut wir für sehr große m abschneiden können, dh wie gut wir den Fehlerterm erhalten können:
Es scheint
e(m) = o(1)
im Allgemeinen unmöglich zu erreichen, aber wir können es hoffentlich beweisene(m)=o(m)
.Das Ganze beruht dann auf der Verteilung der 7-stelligen Ziffern von
5^m
für verschiedene Werte vonm
.Ich bin mir sicher, dass es da draußen eine Menge Theorie gibt, die dies abdeckt. Ich werde vielleicht irgendwann einen Blick darauf werfen und darüber berichten.
quelle
Hier ist eine funktionierende Python-Implementierung von Adams Antwort .
Ich mag es, Algorithmen, die ich mir anschaue, in Python zu werfen, damit ich mit ihnen herumspielen kann. Ich dachte, ich würde sie hier veröffentlichen, in der Hoffnung, dass es für jemanden da draußen nützlich ist, nicht dass es lange gedauert hat, sie zusammen zu werfen.
quelle
rand5()
es sich jedoch um ein anständiges PRNG handelt, ist die Schleife nicht unendlich, da sie letztendlich5*(rand5() - 1) + rand5()
definitiv <= 21 sein wird.)Warum nicht einfach?
Die Wahrscheinlichkeit, in dieser Lösung 1 und 7 zu erhalten, ist aufgrund des Modulos geringer. Wenn Sie jedoch nur eine schnelle und lesbare Lösung wünschen, ist dies der richtige Weg.
quelle
Unter der Annahme, dass Rand (n) hier "zufällige Ganzzahl in einer gleichmäßigen Verteilung von 0 bis n-1 " bedeutet, ist hier ein Codebeispiel unter Verwendung von Pythons Randint, das diesen Effekt hat. Es werden nur Randint (5) und Konstanten verwendet, um den Effekt von Randint (7) zu erzeugen . Eigentlich ein bisschen albern
quelle
do ... while
. Es hätte1337
, oder12345
, oder eine beliebige Anzahl> 1.Die Voraussetzung für die richtige Antwort von Adam Rosenfield lautet:
Wenn n gleich 2 ist, haben Sie 4 Wegwerfmöglichkeiten: y = {22, 23, 24, 25}. Wenn Sie n gleich 6 verwenden, haben Sie nur 1 Wegwerfartikel: y = {15625}.
5 ^ 6 = 15625
7 * 2232 = 15624
Sie rufen rand5 noch öfter an. Sie haben jedoch eine viel geringere Chance, einen Wegwerfwert (oder eine Endlosschleife) zu erhalten. Wenn es eine Möglichkeit gibt, keinen möglichen Wegwerfwert für y zu erhalten, habe ich ihn noch nicht gefunden.
quelle
Hier ist meine Antwort:
Es ist etwas komplizierter als andere, aber ich glaube, es minimiert die Aufrufe von rand5. Wie bei anderen Lösungen besteht eine geringe Wahrscheinlichkeit, dass es zu einer langen Schleife kommt.
quelle
Einfach und effizient:
(Inspiriert von Was ist dein Lieblings-Cartoon "Programmierer"? ).
quelle
Solange nicht mehr sieben Möglichkeiten zur Auswahl stehen, ziehen Sie eine weitere Zufallszahl, die die Anzahl der Möglichkeiten mit fünf multipliziert. In Perl:
quelle
$possibilities
muss immer auf 25 wachsen, um die Schleife zu verlassen und zurückzukehren. Ihr erstes Ergebnis ist also[0-124] % 7
, dass es nicht gleichmäßig verteilt ist, weil125 % 7 != 0
(dies ist tatsächlich 6).Ich mag keine Bereiche ab 1, also fange ich bei 0 an :-)
quelle
from collections import defaultdict def r7(n): if not n: yield [] else: for i in range(1, 6): for j in r7(n-1): yield [i] + j def test_r7(): d = defaultdict(int) for x in r7(6): s = (((((((((x[5] * 5) + x[4]) * 5) + x[3]) * 5) + x[2]) * 5) + x[1]) * 5) + x[0] if s <= 15623: d[s % 7] += 1 print d
Los geht's, gleichmäßige Verteilung und null Rand5-Anrufe.
Das Saatgut muss vorher gesetzt werden.
quelle
Ich weiß, dass es beantwortet wurde, aber scheint das in Ordnung zu sein, aber ich kann Ihnen nicht sagen, ob es eine Voreingenommenheit hat. Meine "Tests" legen nahe, dass dies zumindest vernünftig ist.
Vielleicht wäre Adam Rosenfield so freundlich, einen Kommentar abzugeben?
Meine (naive?) Idee ist folgende:
Akkumulieren Sie rand5, bis genügend zufällige Bits vorhanden sind, um einen rand7 zu erstellen. Dies dauert höchstens 2 Rand5. Um die rand7 Nummer zu bekommen, benutze ich den akkumulierten Wert mod 7.
Um zu vermeiden, dass der Akku überläuft, und da der Akku Mod 7 ist, nehme ich den Mod 7 des Akkus:
Die Funktion rand7 () folgt:
(Ich lasse den Bereich von rand5 0-4 sein und rand7 ist ebenfalls 0-6.)
Bearbeiten: Ergebnisse für 100 Millionen Versuche hinzugefügt.
'Real' Rand Funktionen Mod 5 oder 7
rand5: avg = 1.999802 0: 20003944 1: 19999889 2: 20003690 3: 19996938 4: 19995539 rand7: avg = 3.000111 0: 14282851 1: 14282879 2: 14284554 3: 14288546 4: 14292388 5: 14288736 6: 14280046
Mein rand7
Durchschnitt sieht gut aus und Zahlenverteilungen sehen auch gut aus.
randt: avg = 3.000080 0: 14288793 1: 14280135 2: 14287848 3: 14285277 4: 14286341 5: 14278663 6: 14292943
quelle
Es gibt elegante Algorithmen, die oben zitiert wurden, aber hier ist eine Möglichkeit, sich dem anzunähern, obwohl es sich um einen Kreisverkehr handeln könnte. Ich gehe von Werten aus, die aus 0 generiert wurden.
R2 = Zufallszahlengenerator mit Werten unter 2 (Stichprobenraum = {0, 1})
R8 = Zufallszahlengenerator mit Werten unter 8 (Stichprobenraum = {0, 1, 2, 3, 4, 5, 6, 7) })
Um R8 aus R2 zu generieren, führen Sie R2 dreimal aus und verwenden das kombinierte Ergebnis aller 3 Läufe als Binärzahl mit 3 Ziffern. Hier ist der Wertebereich, wenn R2 dreimal ausgeführt wird:
0 0 0 -> 0
.
.
1 1 1 -> 7
Um nun R7 aus R8 zu generieren, führen wir R7 einfach erneut aus, wenn es 7 zurückgibt:
Die Kreisverkehrslösung besteht darin, R2 aus R5 zu generieren (genau wie wir R7 aus R8 generiert haben), dann R8 aus R2 und dann R7 aus R8.
quelle
Hier ist eine Lösung, die vollständig in ganze Zahlen passt und innerhalb von etwa 4% des Optimums liegt (dh 1,26 Zufallszahlen in {0..4} für jede in {0..6} verwendet). Der Code ist in Scala, aber die Mathematik sollte in jeder Sprache einigermaßen klar sein: Sie nutzen die Tatsache, dass 7 ^ 9 + 7 ^ 8 sehr nahe an 5 ^ 11 liegt. Sie wählen also eine 11-stellige Zahl in Basis 5 aus und interpretieren sie dann als 9-stellige Zahl in Basis 7, wenn sie sich im Bereich befindet (9 Basis-7-Zahlen), oder als 8-stellige Zahl, wenn sie über der 9-stelligen Zahl liegt .:
Wenn Sie einen Test in den Interpreter einfügen (tatsächlich REPL), erhalten Sie:
Die Verteilung ist schön und flach (innerhalb von etwa 10k von 1/7 von 10 ^ 8 in jedem Bin, wie von einer ungefähr-Gaußschen Verteilung erwartet).
quelle
Mit einer rollierenden Summe können Sie beides
Diese beiden Probleme sind ein Problem bei den
rand(5)+rand(5)...
Lösungen vom simplen Typ. Der folgende Python-Code zeigt, wie er implementiert wird (das meiste davon beweist die Verteilung).Und diese Ausgabe zeigt die Ergebnisse:
Eine Vereinfachung
rand(5)+rand(5)
, bei der die Fälle ignoriert werden, in denen mehr als 6 zurückgegeben werden, weist eine typische Abweichung von 18% auf, das 100-fache der oben gezeigten Methode:Und auf Anraten von Nixuz habe ich das Skript aufgeräumt, damit Sie es einfach extrahieren und verwenden können
rand7...
:quelle
Diese Antwort ist eher ein Experiment, um mit der Rand5-Funktion die größtmögliche Entropie zu erzielen. Es ist daher etwas unklar und mit ziemlicher Sicherheit viel langsamer als andere Implementierungen.
Angenommen, die Gleichverteilung von 0-4 und die daraus resultierende Gleichverteilung von 0-6:
Die Anzahl der Bits, die dem Puffer pro Aufruf von Rand5 hinzugefügt werden, beträgt derzeit 4/5 * 2, also 1,6. Wenn der 1/5 Wahrscheinlichkeitswert enthalten ist, der sich um 0,05 erhöht, also 1,65, aber siehe den Kommentar im Code, in dem ich dies deaktivieren musste.
Bits, die durch Aufruf von Rand7 = 3 + 1/8 * (3 + 1/8 * (3 + 1/8 *) verbraucht werden (...
Dies ist 3 + 3/8 + 3/64 + 3/512 ... also ca. 3,42
Durch Extrahieren von Informationen aus den Siebenen fordere ich 1/8 * 1/7 Bits pro Aufruf zurück, also ungefähr 0,018
Dies ergibt einen Nettoverbrauch von 3,4 Bit pro Anruf, was bedeutet, dass das Verhältnis für jeden Rand7 2,125 Anrufe zu Rand5 beträgt. Das Optimum sollte 2.1 sein.
Ich würde mir vorstellen, dass dieser Ansatz erheblich langsamer ist als viele der anderen hier, es sei denn, die Kosten für den Anruf bei Rand5 sind extrem hoch (z. B. das Anrufen einer externen Entropiequelle).
quelle
in php
Schleifen, um eine Zufallszahl zwischen 16 und 127 zu erzeugen, dividieren durch 16, um einen Gleitkommawert zwischen 1 und 7,9375 zu erzeugen, runden dann ab, um einen Int zwischen 1 und 7 zu erhalten. Wenn ich mich nicht irre, besteht eine 16/112-Chance eines der 7 Ergebnisse.
quelle
quelle
7 = 111b
mitp(7) = 8 / 125
Ich glaube, ich habe vier Antworten, von denen zwei exakte Lösungen wie die von @Adam Rosenfield liefern, aber ohne das Endlosschleifenproblem, und die anderen zwei mit nahezu perfekter Lösung, aber schnellerer Implementierung als die erste.
Die beste exakte Lösung erfordert 7 Anrufe
rand5
, aber lassen Sie uns fortfahren, um zu verstehen.Methode 1 - Genau
Die Stärke von Adams Antwort ist, dass es eine perfekte gleichmäßige Verteilung gibt und es eine sehr hohe Wahrscheinlichkeit (21/25) gibt, dass nur zwei Aufrufe von rand5 () benötigt werden. Der schlimmste Fall ist jedoch die Endlosschleife.
Die erste Lösung unten bietet ebenfalls eine perfekte gleichmäßige Verteilung, erfordert jedoch insgesamt 42 Anrufe an
rand5
. Keine Endlosschleifen.Hier ist eine R-Implementierung:
Für Leute, die nicht mit R vertraut sind, gibt es hier eine vereinfachte Version:
Die Verteilung von
rand5
bleibt erhalten. Wenn wir rechnen, hat jede der 7 Iterationen der Schleife 5 ^ 6 mögliche Kombinationen, also die Gesamtzahl der möglichen Kombinationen(7 * 5^6) %% 7 = 0
. Somit können wir die erzeugten Zufallszahlen in gleiche Gruppen von 7 teilen. Weitere Informationen hierzu finden Sie in Methode 2.Hier sind alle möglichen Kombinationen:
Ich denke, es ist einfach zu zeigen, dass Adams Methode viel schneller laufen wird. Die Wahrscheinlichkeit, dass
rand5
in Adams Lösung 42 oder mehr Aufrufe enthalten sind, ist sehr gering ((4/25)^21 ~ 10^(-17)
).Methode 2 - Nicht genau
Nun die zweite Methode, die fast einheitlich ist, aber 6 Aufrufe erfordert
rand5
:Hier ist eine vereinfachte Version:
Dies ist im Wesentlichen eine Iteration von Methode 1. Wenn wir alle möglichen Kombinationen generieren, ergeben sich hier folgende Zählungen:
Eine Zahl wird in
5^6 = 15625
Versuchen noch einmal erscheinen .In Methode 1 verschieben wir nun durch Addition von 1 zu 6 die Zahl 2233 zu jedem der aufeinanderfolgenden Punkte. Somit stimmt die Gesamtzahl der Kombinationen überein. Dies funktioniert, weil 5 ^ 6 %% 7 = 1 ist und wir dann 7 geeignete Variationen durchführen, also (7 * 5 ^ 6 %% 7 = 0).
Methode 3 - Genau
Wenn das Argument von Methode 1 und 2 verstanden wird, folgt Methode 3 und erfordert nur 7 Aufrufe von
rand5
. An diesem Punkt denke ich, dass dies die Mindestanzahl von Anrufen ist, die für eine genaue Lösung erforderlich sind.Hier ist eine R-Implementierung:
Für Leute, die nicht mit R vertraut sind, gibt es hier eine vereinfachte Version:
Die Verteilung von
rand5
bleibt erhalten. Wenn wir rechnen, hat jede der 7 Iterationen der Schleife 5 mögliche Ergebnisse, also die Gesamtzahl der möglichen Kombinationen(7 * 5) %% 7 = 0
. Somit können wir die erzeugten Zufallszahlen in gleiche Gruppen von 7 teilen. Weitere Informationen hierzu finden Sie in Methode eins und zwei.Hier sind alle möglichen Kombinationen:
Ich denke, es ist einfach zu zeigen, dass Adams Methode immer noch schneller läuft. Die Wahrscheinlichkeit, dass
rand5
in Adams Lösung 7 oder mehr Aufrufe enthalten sind, ist immer noch gering ((4/25)^3 ~ 0.004
).Methode 4 - Nicht genau
Dies ist eine geringfügige Variation der zweiten Methode. Es ist fast einheitlich, erfordert jedoch 7 Aufrufe von
rand5
, das ist eine zusätzliche zu Methode 2:Hier ist eine vereinfachte Version:
Wenn wir alle möglichen Kombinationen generieren, ergeben sich folgende Zählungen:
In
5^7 = 78125
Versuchen werden zwei Zahlen einmal weniger angezeigt. Für die meisten Zwecke kann ich damit leben.quelle
i=7
ebenfalls keine Auswirkung, da das Hinzufügen7*rand5()
zur
den Wert vonr
Mod 7 nicht ändert .)Die Funktion, die Sie benötigen, ist rand1_7 () . Ich habe rand1_5 () geschrieben, damit Sie sie testen und zeichnen können.
quelle