Ich beabsichtige nicht, dies für Sicherheitszwecke oder statistische Analysen zu verwenden. Ich muss einen einfachen Zufallszahlengenerator für die Verwendung in meiner Computergrafikanwendung erstellen. Ich möchte den Begriff "Zufallszahlengenerator" nicht verwenden, da die Leute sehr streng darüber nachdenken, aber ich kann mir kein anderes Wort vorstellen, um es zu beschreiben.
Am wichtigsten ist, dass ich den n-ten Term in der Serie in konstanter Zeit berechnen kann.
Es scheint, dass ich dies mit rand_r oder srand () nicht erreichen kann, da diese Bedürfnisse zustandsabhängig sind und ich die nth in einer unbekannten Reihenfolge berechnen muss.
Ich habe lineare Rückführungsschieberegister betrachtet, aber diese sind auch statusabhängig.
Bisher habe ich das:
int rand = (n * prim 1 + Startwert)% prim 2
n = wird verwendet, um den Index des Ausdrucks in der Sequenz anzugeben. ZB: Für erster Term, n == 1
prime 1 und prime 2 sind Primzahlen, bei denen prime 1 & gt; prime 2
seed = eine Zahl, die es erlaubt, dieselbe Funktion zu verwenden erzeuge je nach Samen, aber derselben Serie eine andere Serie für einen bestimmten Samen.
Ich kann nicht sagen, wie gut oder schlecht das ist, da ich es nicht genug benutzt habe, aber es wäre großartig, wenn Leute mit mehr Erfahrung darin die Probleme damit aufzeigen oder mir helfen könnten, es zu verbessern. .
EDIT - Es ist mir egal, ob es vorhersehbar ist. Ich versuche nur etwas Zufälligkeit in meinen Computergrafiken zu erzeugen.
Ich bin vor einer Weile darüber gestolpert und habe nach einer Lösung für dasselbe Problem gesucht. Kürzlich habe ich herausgefunden, wie man es in einer O-Zeit (log (n)) mit niedriger Konstante macht. Dies stimmt zwar nicht ganz mit dem vom Autor angeforderten O (1) überein, aber es kann schnell genug sein (ein Beispiellauf, kompiliert mit -O3, erreicht eine Leistung von 1 Milliarde willkürlicher Index-Zufallszahlen, wobei n zwischen 1 und 2 variiert 48, in 55.7s - knapp vor 18M Zahlen / s).
Erstens, die Theorie hinter der Lösung:
Eine häufige Art von RNGs sind Linear Congruenttial Generators , im Grunde arbeiten sie wie folgt :
zufällig (n) = (m * zufällig (n-1) + b) mod p
Wobei m und b und p Konstanten sind (siehe einen Verweis auf LCGs, wie sie ausgewählt werden). Daraus können wir mit ein bisschen modularer Arithmetik folgendes entwickeln:
%Vor%Das oben beschriebene kann ein Problem sein, da die Zahlen schnell die numerischen Grenzen überschreiten werden. Die Lösung für den generischen Fall besteht darin, m ^ n in modulo mit p * (m - 1) zu berechnen, wenn wir jedoch b = 0 nehmen (ein Unterfall von LCGs, der manchmal Multiplikative kongruente Generatoren ), haben wir eine viel einfachere Lösung und können unsere Berechnungen nur in Modulo p durchführen.
Im Folgenden verwende ich die von RANF verwendeten konstanten Parameter (entwickelt von CRAY) mit p = 2 ^ 48 und g = 44485709377909. Die Tatsache, dass p eine Potenz von 2 ist, reduziert die Anzahl der erforderlichen Operationen (wie erwartet) ):
%Vor%Während ich davon ausgehe, dass der Autor inzwischen weitergegangen ist, wird das hoffentlich für jemand anderen von Nutzen sein.
Wenn Sie wirklich über die Laufzeitperformance besorgt sind, kann das oben genannte um etwa 10x schneller mit Nachschlagetabellen gemacht werden, auf Kosten der Kompilierungszeit und der binären Größe (es ist auch O (1) wrt) der gewünschte Zufallsindex, wie von OP gefordert)
In der folgenden Version habe ich c ++ 14 constexpr verwendet, um die Nachschlagetabellen zur Kompilierzeit zu generieren, und bin zu 176M willkürlichen Index-Zufallszahlen pro Sekunde gekommen (dies hat jedoch etwa 12 zusätzliche Kompilierzeit ergeben) eine Erhöhung der Binärgröße um 1,5 MB - die hinzugefügte Zeit kann abgeschwächt werden, wenn eine teilweise Neukompilierung verwendet wird.
Dies bedeutet im Grunde, dass die Berechnung von beispielsweise m^0xAAAABBBBCCCC mod p in (m^0xAAAA00000000 mod p)*(m^0xBBBB0000 mod p)*(m^CCCC mod p) mod p aufgeteilt wird und die Tabellen dann für jeden der Werte im Bereich 0x0000 - 0xFFFF vorberechnet werden, der% co_de füllen könnte %, AAAA oder BBBB .
RNG im normalen Sinne, haben das Sequenzmuster wie f (n) = S (f (n-1))
Sie haben auch an einem gewissen Punkt die Präzision verloren (wie% mod), aufgrund der Bequemlichkeit der Datenverarbeitung ist es daher nicht möglich, die Folge auf eine Funktion wie X (n) = f (n) = triviale Funktion mit nur n zu erweitern.
Dies bedeutet bestenfalls, dass Sie O (n) damit haben.
Um auf O (1) zu zielen, müssen Sie daher die Idee von f (n) = S (f (n-1)) aufgeben und eine triviale Formel direkt angeben, so dass die N-te Zahl direkt berechnet werden kann ohne zu wissen (N-1) 'th; Dies macht den Samen auch bedeutungslos.
Sie haben also eine einfache Algebra-Funktion und keine Sequenz. Zum Beispiel:
%Vor%Wenn Sie das generierte Muster (wie die Verteilung) stärker einschränken möchten, wird es zu einem komplexen mathematischen Problem.
Aber für Ihr ursprüngliches Ziel, wenn Sie wollen, ist die konstante Geschwindigkeit, um Pseudozufallszahlen zu bekommen, schlage ich vor, es mit traditionellen Zufallszahlengeneratoren zu erzeugen und mit der Nachschlagetabelle zuzugreifen.
BEARBEITEN: Ich habe bemerkt, dass Sie Bedenken wegen einer Tabellengröße für viele Zahlen haben, aber Sie können ein hybrides Modell, wie eine Tabelle mit N Einträgen, einführen und tun f (k) = g (tbl [k% n] , k), die zumindest für eine gute Verteilung über N continue-Sequenz sorgen.
Dies zeigt, dass ein PRNG als Hash-Zähler implementiert ist. Dies scheint den Vorschlag von R. zu kopieren (indem eine Blockchiffre im CTR-Modus als Stream-Chiffre verwendet wurde), aber ich vermied dafür kryptografisch sichere Primitive: für die Geschwindigkeit der Ausführung und weil die Sicherheit kein gewünschtes Merkmal war / p>
Wenn wir versuchen würden, eine sichere Stromchiffre mit Ihrer Anforderung zu erstellen, dass jede emittierte Sequenz trivial wiederholbar sein kann, vorausgesetzt, ihr Index ist bekannt ...
... dann könnten wir einen sicheren Hash-Algorithmus (wie SHA256) und einen Zähler mit vielen Bits wählen (vielleicht 2048 - & gt; Sequenz wiederholt alle 2 ^ 2048 generierten Zahlen ohne erneutes Seeding).
JEDOCH verwendet die Version, die ich hier vorstelle, die berühmte Hash-Funktion von Bob Jenkins (einfach und schnell, aber nicht sicher) zusammen mit einem 64-Bit-Zähler (der so groß ist wie ganze Zahlen auf meinem System, ohne dass eine benutzerdefinierte Inkrementierung erforderlich ist) Code).
Der Code in main zeigt, dass die Kenntnis des RNG-Zählers (Seed) nach der Initialisierung die Wiederholung einer PRNG-Sequenz erlaubt, solange wir wissen, wie viele Werte bis zum Wiederholungspunkt generiert wurden.
Wenn Sie den Wert des Zählers zu einem beliebigen Zeitpunkt in der Ausgabesequenz kennen, können Sie tatsächlich alle zuvor erzeugten Werte UND alle Werte abrufen, die später generiert werden. Dies beinhaltet nur Addieren oder Subtrahieren von Ordinaldifferenzen zu / von einem Referenzzählerwert, der einem bekannten Punkt in der Ausgabesequenz zugeordnet ist.
Es sollte ziemlich einfach sein, diese Klasse für den Einsatz als Testframework anzupassen - Sie könnten andere Hashfunktionen anschließen und die Größe des Zählers ändern, um zu sehen, welche Auswirkungen die Geschwindigkeit hat und wie die generierten Werte verteilt werden (Die einzige Uniformitätsanalyse, die ich gemacht habe, war, nach Mustern in den Bildschirmvollbildern von hexadezimalen Zahlen zu suchen, die von main () gedruckt wurden).
%Vor%