Linear Congruential Generator (LCG) vertritt einen der ältesten und am besten bekannten Pseudozufallszahlengenerator-Algorithmen. Die Theorie hinter ihnen ist leicht zu verstehen, und sie werden leicht durchgeführt und schnell.

Der Generator wird durch die Wiederauftreten-Beziehung definiert:

:

wo die Folge von pseudozufälligen Werten und der ist

: : : :

sind Konstanten der ganzen Zahl, die den Generator angeben. Wenn c = 0, der Generator häufig einen multiplicative congruential Methode oder Lehmer RNG genannt wird. Wenn c  0, der Generator eine congruential Mischmethode genannt wird.

Periode-Länge

Die Periode eines allgemeinen LCG ist am grössten Teil der M, und für einige Wahlen viel weniger als das. Vorausgesetzt, dass c Nichtnull ist, wird der LCG eine volle Periode für alle Samen-Werte wenn und nur wenn haben:

1. und, sind relativ erst

ist

1. durch alle Hauptfaktoren, teilbar

1. ist ein Vielfache 4, wenn ein Vielfache 4 ist.

Während LCGs dazu fähig sind, anständige Pseudozufallszahlen zu erzeugen, ist das zur Wahl der Rahmen c, der M und des a äußerst empfindlich.

Historisch hatten schlechte Wahlen zu unwirksamen Durchführungen von LCGs geführt. Ein besonders veranschaulichendes Beispiel davon ist RANDU, der am Anfang der 1970er Jahre weit verwendet wurde und führen Sie zu vielen Ergebnissen, die zurzeit wegen des Gebrauches dieses schlechten LCG infrage gestellt werden.

Rahmen in der üblichen Anwendung

Die effizientesten LCGs haben eine M gleich einer Macht 2, meistenteils M = 2 oder M = 2, weil das der Modul-Operation erlaubt, durch das bloße Beschneiden von allen außer den niedrigstwertigen 32 oder 64 Bit geschätzt zu werden. Der folgende Tisch verzeichnet die Rahmen von LCGs in der üblichen Anwendung, einschließlich eingebauten rand Funktionen in Laufzeitbibliotheken von verschiedenen Bearbeitern.

Wie gezeigt, oben verwendet LCG'S alle Bit in den Werten nicht immer, die sie erzeugen. Die javanische Durchführung erzeugt 48 Bit mit jeder Wiederholung, aber gibt nur die 32 bedeutendsten Bit von diesen Werten zurück. Das ist, weil die höherwertigen Bit längere Perioden haben als die niedrigeren Ordnungsbit (sieh unten). LCG'S, die diese Technik verwenden, erzeugt viel bessere Werte als diejenigen, die nicht tun.

Vorteile und Nachteile von LCGs

LCGs sind schnell und verlangen, dass minimales Gedächtnis (normalerweise 32 oder 64 Bit) Staat behält. Das macht sie wertvoll, um vielfache unabhängige Ströme vorzutäuschen.

LCGs sollte für Anwendungen nicht verwendet werden, wo Qualitätszufälligkeit kritisch ist. Zum Beispiel ist es für eine Simulation von Monte Carlo wegen der Serienkorrelation (unter anderem) nicht passend. Sie sollten auch für kryptografische Anwendungen nicht verwendet werden; sieh kryptografisch sicheren pseudozufälligen Zahlengenerator für passendere Generatoren. Wenn ein geradliniger congruential Generator mit einem Charakter entsamt und dann einmal wiederholt wird, ist das Ergebnis eine einfache klassische Ziffer genannt eine affine Ziffer; diese Ziffer wird durch die Standardfrequenz-Analyse leicht gebrochen.

LCGs neigen dazu, einige strenge Defekte auszustellen. Zum Beispiel, wenn ein LCG verwendet wird, um Punkte in einem n-dimensional Raum zu wählen, werden die Punkte auf, höchstens, M Hyperflugzeuge (der Lehrsatz von Marsaglia liegen, der von George Marsaglia entwickelt ist). Das ist wegen der Serienkorrelation zwischen aufeinander folgenden Werten der Folge X. Der geisterhafte Test, der ein einfacher Test einer Qualität eines LCG ist, basiert auf dieser Tatsache.

Ein weiteres Problem von LCGs besteht darin, dass die Bit der niedrigeren Ordnung der erzeugten Folge eine viel kürzere Periode haben als die Folge als Ganzes, wenn M auf eine Macht 2 gesetzt wird. Im Allgemeinen wiederholt sich das n-te kleinste positive Ziffer in der Basis b Darstellung der Produktionsfolge, wo b = M für eine ganze Zahl k, mit im grössten Teil der Periode b.

Dennoch kann LCGs eine gute Auswahl sein. Zum Beispiel, in einem eingebetteten System, wird der Betrag des verfügbaren Gedächtnisses häufig streng beschränkt. Ähnlich in einer Umgebung wie eine Videospiel-Konsole, die eine kleine Zahl von Bit der hohen Ordnung eines LCG nimmt, kann gut genügen. Auf die Bit der niedrigen Ordnung von LCGs, wenn M eine Macht 2 ist, sollte für jeden Grad der Zufälligkeit überhaupt nie verlassen werden. Tatsächlich offenbart einfach das Auswechseln 2 für den Modul-Begriff, dass die niedrigen Ordnungsbit sehr kurze Zyklen durchgehen. Insbesondere jeder volle Zyklus LCG, wenn M eine Macht 2 ist, wird abwechselnd gerade und ungerade Ergebnisse erzeugen.

Vergleich mit anderem PRNGs

Wenn höhere Qualitätszufallszahlen erforderlich sind, und genügend Gedächtnis verfügbar ist (~ 2 Kilobytes), dann stellt der Dreher-Algorithmus von Mersenne eine gewaltig längere Periode (2  1) und variate Gleichförmigkeit zur Verfügung. Der Mersenne Dreher erzeugt höhere Qualität geht ab als fast jeder LCG. Eine allgemeine Dreher-Durchführung von Mersenne verwendet interessanterweise genug einen LCG, um Samen-Daten zu erzeugen.

Ein Geradliniges Feed-Back-Verschiebungsregister kann PRNG mit im Wesentlichen demselben Betrag des Gedächtnisses durchgeführt werden und erzeugt einen Strom von Pseudozufallszahlen mit besseren Zufälligkeitsqualitäten, wenn man Ströme von Bit, obgleich mit ein bisschen mehr Berechnung denkt.

Siehe auch

• Voller Zyklus
• Umkehrender congruential Generator
• Multiply-carry
• Lehmer RNG (hat manchmal den Park-Müller RNG genannt)

Referenzen

• D. E. Knuth. Die Kunst der Computerprogrammierung, Bands 2: Halbnumerische Algorithmen, die Dritte Ausgabe. Addison-Wesley, 1997. Internationale Standardbuchnummer 0-201-89684-2. Abschnitt 3.2.1: Die Geradlinige Congruential Methode, Seiten 10-26.
• Sanft, James E., (2003). Zufallszahl-Generation und Monte Carlo Methods, 2. Ausgabe, Springer, internationale Standardbuchnummer 0-387-00178-6.

• (in dieser Zeitung wird um effiziente Algorithmen gegeben, Folgen abzuleiten, die durch bestimmte pseudozufällige Zahlengeneratoren erzeugt sind).

Links

• Die Simulation Geradliniger Congruential Generator vergegenwärtigt sich die Korrelationen zwischen den pseudozufälligen Zahlen, wenn sie die Rahmen manipuliert.
• Sicherheit der Zufallszahl-Generation: Eine kommentierte Bibliografie
• Geradlinige Congruential Generatoren eilen zu sci.math dahin
• Der "Tod des" Kunstcomputerkunstprojektes an Goldstein Technologies LLC, verwendet einen LCG, um 33,554,432 Images zu erzeugen

• P. L'Ecuyer und R. Simard, ``TestU01: Eine C Bibliothek für die Empirische Prüfung von Zufallszahlengeneratoren, Mai 2006, Revidierter November 2006, ACM Transaktionen auf der Mathematischen Software, 33, 4, Artikel 22, August 2007.]
• Congruential zusätzliche Methode: Mathematik und Logik hinter seiner Ausbreitung