Wie kann ich die Periode meines Pseudozufallszahlengenerators bestimmen?

14

Angenommen, ich verwende einen linearen kongruenten Pseudozufallszahlengenerator (PRNG). Wie kann ich bei gegebenem Startwert , Multiplikationsfaktor (a), Verschiebungsfaktor (c) und Modulfaktor (m) die Periode meines PRNG bestimmen? Ermittle ich es durch Experimentier- / Mustererkennungsalgorithmen, oder gibt es eine direkte Formel zur Berechnung seiner Periode? x0

Obwohl meine Frage speziell die lineare Kongruenzmethode betrifft, bin ich offen dafür, mehr darüber zu erfahren, wie Perioden in der Praxis auch für andere PRNG berechnet werden.

random-number-generation Paul
quelle
Relevant: en.wikipedia.org/wiki/…
Übrigens, wenn Sie LFSR verwenden, ist die Periode maximal, wenn das Rückkopplungspolynom primitiv ist . In einem solchen Fall ist die Periode AFAIK (zitiere mich nicht; zu faul, um meine Kursnotizen aufzuarbeiten) wobei das Rückkopplungspolynom p ( x ) ∈ F q [ x ] des Grades n ist und q die Größe von ist das Feld der Koeffizienten. qnp(x)∈Fq[x]nq
2
Floyds Zykluserkennungsalgorithmen sowie Brents Zykluserkennungsalgorithmen sind beide effiziente Methoden zur Erkennung von Zyklen. Beide geben ein Vielfaches von L der Periode zurück, und sobald Sie das haben, können Sie L faktorisieren und sehen, welcher der kleinste Faktor ist, der eine Periode ist.
Xdavidliu

Antworten:

12

Wenn Sie sich auf LCG- PRNGs mit vollem Zyklus beschränken, ist die Antwort per Definition einfach m . m

Um den Zeitraum eines nicht vollständigen LCG-PRNG-Zyklus für einen bestimmten Startwert zu ermitteln, müssen Sie nur die Anzahl der Iterationen des PRNG zählen, bis der Startwert erneut generiert wird.

Von der referenzierten Wikipedia-Seite :

Periodenlänge

Die Periode einer allgemeinen LCG beträgt höchstens m , und für einige Entscheidungen viel weniger. Vorausgesetzt, dass c ungleich Null ist, hat die LCG einen vollständigen Zeitraum für alle Startwerte, und zwar genau dann, wenn :

  • c undm sindrelativ prim,
  • ein-1 ist teilbar durch allePrimfaktorenvonm
  • ein-1 ist ein Vielfaches von 4, wennm ein Vielfaches von 4 ist.

Während LCGs in der Lage sind, anständige Pseudozufallszahlen zu erzeugen , ist dies äußerst empfindlich für die Wahl der Parameter c , m und ein .

In der Vergangenheit hatten schlechte Entscheidungen zu ineffektiven Implementierungen von LCGs geführt. Ein besonders anschauliches Beispiel hierfür ist RANDU, das in den frühen 1970er Jahren weit verbreitet war und zu vielen Ergebnissen führte, die derzeit aufgrund der Verwendung dieses schlechten LCG in Frage gestellt werden.

Warum Sie einen Vollzyklusgenerator verwenden möchten

Wenn Sie sich nicht auf LCG-PRNGs mit vollem Zyklus beschränken, gehen Sie ein großes Risiko ein .

Wenn Sie nicht wissen, dass eine bestimmte LCG einen vollständigen Zyklus hat, könnten Sie einen Generator mit einer beliebigen Anzahl von voneinander verschiedenen Sequenzen erhalten, von denen einige peinlich klein und schrecklich zufällig sein können, möglicherweise sogar noch schlimmer als der berüchtigte RANDU- Generator .

Sie möchten wirklich nicht jeden möglichen Startwert überprüfen müssen, um sicherzustellen, dass er eine Sequenz generiert, die für Ihre Anwendung lang genug ist.

Weitere Lektüre

Für eine exzellente Einführung in Pseudozufallszahlengeneratoren empfehle ich dringend, das Kapitel Numerische Rezepte über Zufallszahlen zu lesen .

Mark Booth
quelle
Das ist wahr, aber ich beschränke mich nicht auf LCG PRNGs für die gesamte Periode ... Ich bin neugierig auf die schlechten Entscheidungen von a, c und m, so dass die Zufallsströme, die nicht die gesamte Periode erreichen. Ich möchte im Voraus wissen können, wie die Periode bei einigen a, c und m unweigerlich sein wird. Ich weiß, dass es durch m begrenzt ist, aber ich habe mich gefragt, ob wir es besser machen und den genauen Zeitraum ermitteln können.
Paul
Ich glaube nicht, dass dies eine technische Frage ist: Die Frage lautete "wie man die Periode eines LCG mit beliebigen Parametern bestimmt", während diese Antwort besagt: "Benutze keine willkürlichen LCGs, benutze immer Vollperioden-LCGs, und wenn Sie dies annehmen , wäre die Antwort auf Ihre Frage per definitionem der maximal mögliche Zeitraum. " Das in dieser Antwort dargelegte Argument für die Verwendung von Vollperioden-LCFs ist vollkommen überzeugend, aber das Problem ist, dass die Frage überhaupt nicht danach gerichtet ist.
Xdavidliu
Entschuldigung @xdavidliu, aber ich sehe nicht, wie Ihr neuer Kommentar mir hilft, meine Antwort zu verbessern. Sie haben mich darauf aufmerksam gemacht, dass ich die Frage nicht wirklich beantwortet habe. Ich habe meine Antwort bearbeitet, um das zu beheben, und Sie dann in einer Weise informiert, von der ich dachte, dass sie Sie zum Lächeln bringen könnte (wenn Sie ein Futurama-Fan sind). Ich sehe nicht, dass mehr gesagt werden muss.
Mark Booth
Beachten Sie, dass Kommentare beim Stapelaustausch nicht für längere Diskussionen vorgesehen sind, für die Computational Science Chat verwendet wird . Kommentare dienen dazu, Fragen und Antworten zu verbessern, und lenken ab. Deshalb versuchen wir, sie auf ein Minimum zu beschränken. Kommentare sollten als kurzlebig angesehen werden. Jeder Kommentar, der nicht mehr aktiv zur Verbesserung einer Frage oder Antwort beiträgt, kann jederzeit gelöscht werden, um einen Beitrag aufzuräumen .
Mark Booth