Linearer Kongruenzgenerator – Wikipedia

before-content-x4

Zwei Modulo-9-LCGs zeigen, wie unterschiedliche Parameter zu unterschiedlichen Zykluslängen führen. Jede Zeile zeigt den Zustand, der sich entwickelt, bis er sich wiederholt. Die obere Reihe zeigt einen Generator mit m = 9, ein = 2, c = 0 und ein Startwert von 1, der einen Zyklus der Länge 6 erzeugt. Die zweite Reihe ist der gleiche Generator mit einem Startwert von 3, der einen Zyklus der Länge 2 erzeugt ein = 4 und c = 1 (untere Reihe) ergibt eine Zykluslänge von 9 mit jedem Samen in [0, 8].

EIN linearer Kongruenzgenerator ((LCG) ist ein Algorithmus, der eine Folge von pseudozufälligen Zahlen liefert, die mit einer diskontinuierlichen stückweise linearen Gleichung berechnet werden. Das Verfahren repräsentiert einen der ältesten und bekanntesten Algorithmen zur Erzeugung von Pseudozufallszahlen.[1] Die Theorie dahinter ist relativ einfach zu verstehen und sie sind leicht zu implementieren und schnell, insbesondere auf Computerhardware, die durch Abschneiden von Speicherbits eine modulare Arithmetik liefern kann.

Der Generator wird durch die Wiederholungsrelation definiert:

wo

X.{ displaystyle X}

ist die Folge von Pseudozufallswerten und

sind ganzzahlige Konstanten, die den Generator angeben. Wenn c = 0, der Generator wird oft als a bezeichnet multiplikativer Kongruenzgenerator (MCG) oder Lehmer RNG. Wenn c ≠ 0 heißt die Methode a gemischter Kongruenzgenerator.[2]::4-

Wann c ≠ 0, ein Mathematiker würde die Wiederholung als affine Transformation bezeichnen, nicht als lineare, aber die Fehlbezeichnung ist in der Informatik gut etabliert.[3]::1

Periodenlänge[edit]

Ein Vorteil von LCGs besteht darin, dass bei entsprechender Auswahl der Parameter der Zeitraum bekannt und lang ist. Obwohl dies nicht das einzige Kriterium ist, ist eine zu kurze Periode ein schwerwiegender Fehler in einem Pseudozufallszahlengenerator.[4]

Während LCGs in der Lage sind, Pseudozufallszahlen zu erzeugen, die formale Tests auf Zufälligkeit bestehen können, ist die Qualität der Ausgabe äußerst empfindlich gegenüber der Wahl der Parameter m und ein.[5][2][6][7][8][3] Zum Beispiel, ein = 1 und c = 1 erzeugt ein einfaches Modulo-m Zähler, der eine lange Periode hat, aber offensichtlich nicht zufällig ist.

Historisch gesehen schlechte Entscheidungen für ein haben 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.[9]

Es gibt drei gängige Familien für die Parameterauswahl:

m Prime, c = 0[edit]

Dies ist die ursprüngliche Lehmer RNG-Konstruktion. Der Zeitraum ist m−1 wenn der Multiplikator ein wird als primitives Element der Ganzzahlen modulo gewählt m. Der Ausgangszustand muss zwischen 1 und 1 gewählt werden m−1.

Ein Nachteil eines Primzahlmoduls besteht darin, dass die modulare Reduktion ein Produkt mit doppelter Breite und einen expliziten Reduktionsschritt erfordert. Oft wird eine Primzahl von weniger als einer Potenz von 2 verwendet (die Mersenne-Primzahlen 2)31−1 und 261−1 sind beliebt), so dass die Reduktion modulo m = 2e – – d kann berechnet werden als (Axt mod 2e) + dAxt/ 2e⌋. Darauf muss eine bedingte Subtraktion von folgen m Wenn das Ergebnis zu groß ist, die Anzahl der Subtraktionen jedoch auf begrenzt ist Anzeige/.m, die leicht auf eins beschränkt werden kann, wenn d ist klein.

Wenn ein Produkt mit doppelter Breite nicht verfügbar ist und der Multiplikator sorgfältig ausgewählt wird, Schrages Methode[10] könnte genutzt werden. Um dies zu tun, Faktor m = qa+rdh q = ⌊m/.ein und r = m mod ein. Dann berechnen Axt mod m = ein((x mod q) – rx/.q. Schon seit x mod q < qm/.einist der erste Term streng kleiner als bin /.ein= m . Wenn ein wird so gewählt, dass rq(und somit r /.q≤ 1), dann ist auch der zweite Term kleiner als m:: rx/.q ⌋ ≤ rx/.q= x((r /.q) ≤ x < m . Somit können beide Produkte mit einem Produkt mit einfacher Breite berechnet werden, und der Unterschied zwischen ihnen liegt im Bereich [1−mm−1]kann also auf reduziert werden [0, m−1] mit einer einzigen bedingten Addition.[11]

Ein zweiter Nachteil ist, dass es umständlich ist, den Wert 1 ≤ umzuwandeln x < m zu einheitlichen Zufallsbits. Wenn eine Primzahl von weniger als einer Potenz von 2 verwendet wird, werden die fehlenden Werte manchmal einfach ignoriert.

m eine Potenz von 2, c = 0[edit]

Wählen m meistens eine Potenz von 2 sein m= 232 oder m = 264erzeugt ein besonders effizientes LCG, da dadurch die Moduloperation durch einfaches Abschneiden der Binärdarstellung berechnet werden kann. Tatsächlich werden die höchstwertigen Bits normalerweise überhaupt nicht berechnet. Es gibt jedoch Nachteile.

Diese Form hat maximale Periode m / 4, erreicht wenn ein ≡ 3 oder ein ≡ 5 (Mod 8). Der Ausgangszustand X.0 muss ungerade sein und die niedrigen drei Bits von X. wechseln zwischen zwei Zuständen und sind nicht nützlich. Es kann gezeigt werden, dass diese Form einem Generator mit einem Modul von einem Viertel der Größe und entspricht c ≠ 0.[2]

Ein schwerwiegenderes Problem bei der Verwendung eines Zweierpotenzmoduls besteht darin, dass die niedrigen Bits eine kürzere Periode haben als die hohen Bits. Das Bit niedrigster Ordnung von X. Ändert sich nie (X. ist immer ungerade) und die nächsten zwei Bits wechseln zwischen zwei Zuständen. (Wenn ein ≡ 5 (mod 8), dann ändert sich Bit 1 nie und Bit 2 wechselt. Wenn ein ≡ 3 (mod 8), dann ändert sich Bit 2 nie und Bit 1 wechselt.) Bit 3 wiederholt sich mit einer Periode von 4, Bit 4 hat eine Periode von 8 und so weiter. Nur das bedeutendste Stück von X. erreicht die volle Periode.

c≠ 0[edit]

Wann c≠ 0, richtig gewählte Parameter erlauben eine Periode gleich m für alle Startwerte. Dies geschieht genau dann, wenn:[2]::17-19

Diese drei Anforderungen werden als Hull-Dobell-Theorem bezeichnet.[12][13]

Dieses Formular kann mit jedem verwendet werden m , funktioniert aber nur gut für m mit vielen wiederholten Primfaktoren, wie einer Potenz von 2; Die Verwendung der Wortgröße eines Computers ist die häufigste Wahl. Wenn mwäre eine quadratfreie ganze Zahl, würde dies nur erlauben ein ≡ 1 (mod m ), was ein sehr schlechtes PRNG ergibt; Eine Auswahl möglicher Vollzeitmultiplikatoren ist nur verfügbar, wenn m hat Primfaktoren wiederholt.

Obwohl das Hull-Dobell-Theorem eine maximale Periode vorsieht, reicht es nicht aus, a zu garantieren gut Generator. Zum Beispiel ist es wünschenswert für ein – 1 nicht mehr durch Primfaktoren von teilbar sein m als nötig. Also wenn m ist also eine Potenz von 2 ein – 1 sollte durch 4 teilbar sein, aber nicht durch 8 teilbar, dh ein ≡ 5 (Mod 8).[2]::§3.2.1.3

In der Tat erzeugen die meisten Multiplikatoren eine Sequenz, die den einen oder anderen Test auf Nicht-Zufälligkeit nicht besteht, und finden einen Multiplikator, der alle anwendbaren Kriterien erfüllt[2]::§3.3.3 ist ziemlich herausfordernd. Der Spektraltest ist einer der wichtigsten Tests.[14]

Beachten Sie, dass ein Potenz-2-Modul das oben beschriebene Problem teilt c = 0: das Tief kBits bilden einen Generator mit Modul 2k und somit mit einer Periode von 2 wiederholenk;; nur das höchstwertige Bit erreicht die volle Periode. Wenn eine Pseudozufallszahl kleiner als rist erwünscht, ⌊rX /.m⌋ ist ein Ergebnis von viel höherer Qualität als X. mod r. Leider erleichtern die meisten Programmiersprachen das Schreiben von letzteren erheblich (X % r), also ist es die am häufigsten verwendete Form.

Der Generator ist nicht empfindlich auf die Wahl von c , solange es relativ prim zum Modul ist (zB wenn mist also eine Potenz von 2 c muss ungerade sein), also der Wert c= 1 wird üblicherweise gewählt.

Die Serie produziert von anderen Entscheidungen von c kann als einfache Funktion der Serie geschrieben werden, wenn c= 1.[2]::11 Insbesondere wenn Y.ist die prototypische Serie definiert durch Y.0 = 0 und Y.n +1 = aYn+1 mod m, dann eine allgemeine Reihe X.n +1 = Axtn+cmod m kann als affine Funktion von geschrieben werden Y. ::

Im Allgemeinen zwei beliebige Serien X. und Z. mit dem gleichen Multiplikator und Modul sind durch verbunden

Häufig verwendete Parameter[edit]

In der folgenden Tabelle sind die Parameter der häufig verwendeten LCGs aufgeführt, einschließlich der integrierten rand () Funktionen in Laufzeitbibliotheken verschiedener Compiler. Diese Tabelle soll die Popularität zeigen, keine zu emulierenden Beispiele. Viele dieser Parameter sind schlecht. Tabellen mit guten Parametern sind verfügbar.[8][3]

Quelle Modul
m
Multiplikator
ein
Zuwachs
c
Ausgangsbits von Seed in rand () oder Zufällig (L)
Numerische Rezepte 2³² 1664525 1013904223
Borland C / C ++ 2³² 22695477 1 Bits 30..16 in rand () 30,0 Zoll lrand ()
glibc (von GCC verwendet)[15] 2³¹ 1103515245 12345 Bits 30..0
ANSI C: Watcom, Digital Mars, CodeWarrior und IBM VisualAge C / C ++ [16]
C90, C99, C11: Vorschlag in der ISO / IEC 9899,[17]C18
2³¹ 1103515245 12345 Bits 30..16
Borland Delphi, virtueller Pascal 2³² 134775813 1 Bits 63..32 von (Samen × L)
Turbo Pascal 2³² 134775813 (8088405₁₆) 1
Microsoft Visual / Quick C / C ++ 2³² 214013 (343FD₁₆) 2531011 (269EC3₁₆) Bits 30..16
Microsoft Visual Basic (6 und früher)[18] 2²⁴ 1140671485 (43FD43FD₁₆) 12820163 (C39EC3₁₆)
RtlUniform von Native API[19] 2³¹ – 1 2147483629 (7FFFFFED₁₆) 2147483587 (7FFFFFC3₁₆)
Apple CarbonLib, C ++ 11 minstd_rand0[20] 2³¹ – 1 16807 0 siehe MINSTD
C ++ 11 minstd_rand[20] 2³¹ – 1 48271 0 siehe MINSTD
MMIX von Donald Knuth 2⁶⁴ 6364136223846793005 1442695040888963407
Newlib, Musl 2⁶⁴ 6364136223846793005 1 Bits 63..32
VMS MTH $ ZUFÄLLIG,[21] alte Versionen von glibc 2³² 69069 (10DCD₁₆) 1
Javas java.util.Random, POSIX [ln]rand48, glibc [ln]rand48[_r] 2⁴⁸ 25214903917 (5DEECE66D₁₆) 11 Bits 47..16

random0[22][23][24][25][26]

134456 = 2³7⁵ 8121 28411
POSIX[27] [jm]rand48, glibc [mj]rand48[_r] 2⁴⁸ 25214903917 (5DEECE66D₁₆) 11 Bits 47..15
POSIX [de]rand48, glibc [de]rand48[_r] 2⁴⁸ 25214903917 (5DEECE66D₁₆) 11 Bits 47..0
cc65[28] 2²³ 65793 (10101₁₆) 4282663 (415927₁₆) Bits 22..8
cc65 2³² 16843009 (1010101₁₆) 826366247 (31415927₁₆) Bits 31..16
Früher üblich: RANDU [9] 2³¹ 65539 0

Wie oben gezeigt, verwenden LCGs nicht immer alle Bits in den von ihnen erzeugten Werten. Beispielsweise arbeitet die Java-Implementierung bei jeder Iteration mit 48-Bit-Werten, gibt jedoch nur die 32 höchstwertigen Bits zurück. Dies liegt daran, dass die Bits höherer Ordnung längere Perioden haben als die Bits niedrigerer Ordnung (siehe unten). LCGs, die diese Kürzungstechnik verwenden, liefern statistisch bessere Werte als solche, die dies nicht tun. Dies macht sich insbesondere bei Skripten bemerkbar, die die Mod-Operation verwenden, um die Reichweite zu verringern. Das Ändern der Zufallszahl Mod 2 führt dazu, dass 0 und 1 ohne Kürzung abwechseln.

Vorteile und Nachteile[edit]

LCGs sind schnell und benötigen nur minimalen Speicher (ein Modulo-)mZahl, oft 32 oder 64 Bit), um den Status beizubehalten. Dies macht sie wertvoll für die Simulation mehrerer unabhängiger Streams. LCGs sind nicht für kryptografische Anwendungen vorgesehen und dürfen nicht verwendet werden. Verwenden Sie für solche Anwendungen einen kryptografisch sicheren Pseudozufallszahlengenerator.

Obwohl LCGs einige spezifische Schwächen aufweisen, sind viele ihrer Mängel auf einen zu kleinen Zustand zurückzuführen. Die Tatsache, dass Menschen seit so vielen Jahren dazu gebracht werden, sie mit so kleinen Modulen zu verwenden, kann als Beweis für die Stärke der Technik angesehen werden. Ein LCG mit einem ausreichend großen Zustand kann sogar strenge statistische Tests bestehen. Ein Modulo-2-LCG, das die hohen 32 Bit zurückgibt, besteht die SmallCrush-Suite von TestU01.[citation needed] und ein 96-Bit-LCG besteht die strengste BigCrush-Suite.[29]

Für ein bestimmtes Beispiel wird erwartet, dass ein idealer Zufallszahlengenerator mit 32 Bit Ausgabe (nach dem Geburtstagssatz) nachher beginnt, frühere Ausgaben zu duplizieren m ≈ 216 Ergebnisse. Irgendein PRNG, dessen Ausgabe der vollständige, nicht abgeschnittene Zustand ist, erzeugt erst nach Ablauf des gesamten Zeitraums Duplikate, ein leicht erkennbarer statistischer Fehler. Aus verwandten Gründen sollte jedes PRNG einen Zeitraum haben, der länger als das Quadrat der Anzahl der erforderlichen Ausgänge ist. Bei modernen Computergeschwindigkeiten bedeutet dies einen Zeitraum von 264 für alle außer den am wenigsten anspruchsvollen Anwendungen und länger für anspruchsvolle Simulationen.

Ein für LCGs spezifischer Fehler besteht darin, dass bei Auswahl von Punkten in einem n-dimensionalen Raum die Punkte höchstens auf liegen. nn! ⋅m Hyperebenen (Marsaglias Theorem, entwickelt von George Marsaglia).[5] Dies ist auf die serielle Korrelation zwischen aufeinanderfolgenden Werten der Sequenz zurückzuführen X.n. Unachtsam ausgewählte Multiplikatoren haben normalerweise weit weniger Ebenen mit großem Abstand, was zu Problemen führen kann. Der Spektraltest, bei dem es sich um einen einfachen Test der Qualität eines LCG handelt, misst diesen Abstand und ermöglicht die Auswahl eines guten Multiplikators.

Der Ebenenabstand hängt sowohl vom Modul als auch vom Multiplikator ab. Ein ausreichend großer Modul kann diesen Abstand unter die Auflösung von Zahlen mit doppelter Genauigkeit reduzieren. Die Wahl des Multiplikators wird weniger wichtig, wenn der Modul groß ist. Es ist immer noch notwendig, den Spektralindex zu berechnen und sicherzustellen, dass der Multiplikator kein schlechter ist, aber rein wahrscheinlich wird es äußerst unwahrscheinlich, dass ein schlechter Multiplikator auftritt, wenn der Modul größer als etwa 2 ist64.

Ein weiterer Fehler, der für LCGs spezifisch ist, ist die kurze Periode der niederwertigen Bits, wenn m wird als Potenz von 2 gewählt. Dies kann durch Verwendung eines Moduls, der größer als die erforderliche Ausgabe ist, und unter Verwendung der höchstwertigen Bits des Zustands gemindert werden.

Für einige Anwendungen können LCGs jedoch eine gute Option sein. Beispielsweise ist in einem eingebetteten System die verfügbare Speichermenge häufig stark begrenzt. In ähnlicher Weise kann in einer Umgebung wie einer Videospielkonsole das Aufnehmen einer kleinen Anzahl von Bits höherer Ordnung eines LCG durchaus ausreichen. (Die niederwertigen Bits von LCGs, wenn m eine Potenz von 2 ist, sollten niemals für irgendeinen Grad an Zufälligkeit verwendet werden.) Die niederwertigen Bits durchlaufen sehr kurze Zyklen. Insbesondere erzeugt jedes Vollzyklus-LCG, wenn m eine Potenz von 2 ist, abwechselnd ungerade und gerade Ergebnisse.

LCGs sollten sehr sorgfältig auf ihre Eignung für nicht kryptografische Anwendungen geprüft werden, bei denen eine hohe Zufälligkeit von hoher Qualität von entscheidender Bedeutung ist. Für Monte-Carlo-Simulationen muss ein LCG einen Modul verwenden, der größer und vorzugsweise viel größer als der Würfel der Anzahl der erforderlichen Zufallsstichproben ist. Dies bedeutet zum Beispiel, dass ein (gutes) 32-Bit-LCG verwendet werden kann, um ungefähr tausend Zufallszahlen zu erhalten; Ein 64-Bit-LCG ist gut für ungefähr 221 Zufallsstichproben (etwas mehr als zwei Millionen) usw. Aus diesem Grund sind LCGs in der Praxis nicht für groß angelegte Monte-Carlo-Simulationen geeignet.

Beispiel für Python-Code[edit]

Das Folgende ist eine Implementierung einer LCG in Python:

def lcg(modulus, a, c, seed):
    """Linear congruential generator."""
    while True:
        seed = (a * seed + c) % modulus
        yield seed

Beispiel für einen kostenlosen Pascal-Code[edit]

Free Pascal verwendet einen Mersenne Twister als Standard-Pseudozufallszahlengenerator, während Delphi eine LCG verwendet. Hier ist ein Delphi-kompatibles Beispiel in Free Pascal, basierend auf den Informationen in der obigen Tabelle. Bei gleichem RandSeed-Wert wird dieselbe Folge von Zufallszahlen wie bei Delphi generiert.

unit lcg_random;
{$ifdef fpc}{$mode delphi}{$endif}
interface

function LCGRandom: extended; overload;inline;
function LCGRandom(const range:longint):longint;overload;inline;

implementation
function IM:cardinal;inline;
begin
  RandSeed := RandSeed * 134775813 + 1;
  Result := RandSeed;
end;

function LCGRandom: extended; overload;inline;
begin
  Result := IM * 2.32830643653870e-10;
end;

function LCGRandom(const range:longint):longint;overload;inline;
begin
  Result := IM * range shr 32;
end;

Wie alle Pseudozufallszahlengeneratoren muss eine LCG den Status jedes Mal speichern und ändern, wenn sie eine neue Nummer generiert. Mehrere Threads können gleichzeitig auf diesen Status zugreifen, was zu einer Racebedingung führt. Implementierungen sollten unterschiedliche Status mit jeweils eindeutiger Initialisierung für unterschiedliche Threads verwenden, um gleiche Folgen von Zufallszahlen bei gleichzeitiger Ausführung von Threads zu vermeiden.

LCG-Derivate[edit]

Es gibt mehrere Generatoren, die lineare Kongruenzgeneratoren in unterschiedlicher Form sind, und daher können die zur Analyse von LCGs verwendeten Techniken auf sie angewendet werden.

Ein Verfahren zum Erzeugen eines längeren Zeitraums besteht darin, die Ausgaben mehrerer LCGs verschiedener Zeiträume mit einem großen kleinsten gemeinsamen Vielfachen zu summieren; Der Wichmann-Hill-Generator ist ein Beispiel für diese Form. (Wir würden es vorziehen, wenn sie vollständig koprime sind, aber ein Primmodul impliziert eine gerade Periode, daher muss mindestens ein gemeinsamer Faktor 2 vorhanden sein.) Dies kann als äquivalent zu einem einzelnen LCG mit einem Modul gleich dem gezeigt werden Produkt der Komponente LCG-Module.

Marsaglias Add-with-Carry- und Subtrah-with-Borrow-PRNGs mit einer Wortgröße von b = 2w und hinkt r und s((r > s) entsprechen LCGs mit einem Modul von br ± bs ± 1.[30][31]

Multiplizieren Sie mit Carry-PRNGs mit einem Multiplikator von ein sind äquivalent zu LCGs mit einem großen Primmodul von abr−1 und ein Potenz-2-Multiplikator b.

Ein permutierter Kongruenzgenerator beginnt mit einem LCG mit einer Leistung von 2 Modulen und wendet eine Ausgangstransformation an, um das Kurzzeitproblem in den niederwertigen Bits zu beseitigen.

Vergleich mit anderen PRNGs[edit]

Das andere weit verbreitete Grundelement zum Erhalten von Pseudozufallssequenzen mit langer Periode ist die lineare Rückkopplungsschieberegisterkonstruktion, die auf der Arithmetik in GF basiert (2).[x]der Polynomring über GF (2). Anstelle einer ganzzahligen Addition und Multiplikation sind die Grundoperationen eine Exklusiv- oder Übertrag-Multiplikation, die normalerweise als Folge logischer Verschiebungen implementiert wird. Diese haben den Vorteil, dass alle ihre Bits vollperiodisch sind; Sie leiden nicht unter der Schwäche der niederwertigen Bits, die das arithmetische Modulo 2 plagenk.[32]

Beispiele für diese Familie sind Xorshift-Generatoren und der Mersenne-Twister. Letzteres bietet einen sehr langen Zeitraum (219937−1) und variieren die Gleichmäßigkeit, aber es bestehen einige statistische Tests nicht.[33]Verzögerte Fibonacci-Generatoren fallen ebenfalls in diese Kategorie. Obwohl sie eine arithmetische Addition verwenden, wird ihre Periode durch ein LFSR unter den niedrigstwertigen Bits sichergestellt.

Es ist leicht, die Struktur eines linearen Rückkopplungsschieberegisters mit geeigneten Tests zu erfassen[34] wie der in der TestU01-Suite implementierte lineare Komplexitätstest; Eine aus aufeinanderfolgenden Bits eines LFSR initialisierte boolesche zirkulierende Matrix hat niemals einen höheren Rang als den Grad des Polynoms. Das Hinzufügen einer nichtlinearen Ausgangsmischfunktion (wie bei den Konstruktionen xoshiro256 ** und permutierter kongruenter Generatoren) kann die Leistung bei statistischen Tests erheblich verbessern.

Eine weitere Struktur für ein PRNG ist eine sehr einfache Wiederholungsfunktion in Kombination mit einer leistungsstarken Ausgangsmischfunktion. Dies umfasst Blockchiffren im Zählermodus und nicht kryptografische Generatoren wie z SplitMix64.

Eine Struktur ähnlich wie LCGs, aber nichtäquivalent ist der mehrfach rekursive Generator: X.n = (ein1X.n−1 + ein2X.n −2 + ··· + einkX.n – –k) mod mzum k≥ 2. Mit einem Primzahlmodul können Perioden bis zu erzeugt werden mk−1, also eine nützliche Erweiterung der LCG-Struktur auf größere Zeiträume.

Eine leistungsstarke Technik zum Erzeugen hochwertiger Pseudozufallszahlen besteht darin, zwei oder mehr PRNGs unterschiedlicher Struktur zu kombinieren. Die Summe aus einem LFSR und einem LCG (wie bei den KISS- oder Xorwow-Konstruktionen) kann bei einigen Geschwindigkeitskosten sehr gut funktionieren.

Siehe auch[edit]

  1. ^ “”Lineare Kongruenzgeneratoren“von Joe Bolte, Wolfram Demonstrationsprojekt.
  2. ^ ein b c d e f G Knuth, Donald (1997). Seminumerische Algorithmen. Die Kunst der Computerprogrammierung. 2 (3. Aufl.). Reading, MA: Addison-Wesley Professional. S. 10–26.
  3. ^ ein b c Steele, Guy; Vigna, Sebastiano (15. Januar 2020). “Rechenlich einfache, spektral gute Multiplikatoren für kongruente Pseudozufallszahlengeneratoren”. arXiv:2001.05304 [cs.DS]. Zu diesem Zeitpunkt ist es unwahrscheinlich, dass die heute traditionellen Namen korrigiert werden.Mathematik der Berechnung (erscheint). Zugehörige Daten bei https://github.com/vigna/CPRNG.
  4. ^ L’Ecuyer, Pierre (13. Juli 2017). Chan, WKV; D’Ambrogio, A.; Zacharewicz, G.; Mustafee, N.; Wainer, G.; Page, E. (Hrsg.). Geschichte der einheitlichen Zufallszahlengenerierung (PDF). Tagungsband der Wintersimulationskonferenz 2017 (erscheint). Las Vegas, Vereinigte Staaten. hal-01561551.
  5. ^ ein b Marsaglia, George (September 1968). “Zufallszahlen fallen hauptsächlich in die Flugzeuge” (PDF). PNAS. 61 (1): 25–28. Bibcode:1968PNAS … 61 … 25M. doi:10.1073 / pnas.61.1.25. PMC 285899. PMID 16591687.
  6. ^ Park, Stephen K.; Miller, Keith W. (Oktober 1988). “Zufallszahlengeneratoren: Gute sind schwer zu finden” (PDF). Mitteilungen der ACM. 31 (10): 1192–1201. doi:10.1145 / 63039.63042.
  7. ^ Hörmann, Wolfgang; Derflinger, Gerhard (1993). “Ein tragbarer einheitlicher Zufallszahlengenerator, der für die Ablehnungsmethode gut geeignet ist” (PDF). ACM-Transaktionen mit mathematischer Software . 19 (4): 489–495. CiteSeerX 10.1.1.52.3811. doi:10.1145 / 168173.168414. ein Multiplikator ungefähr so ​​klein wie merzeugt Zufallszahlen mit einer schlechten eindimensionalen Verteilung.
  8. ^ ein b L’Ecuyer, Pierre (1999). “Tabellen linearer Kongruenzgeneratoren unterschiedlicher Größe und guter Gitterstruktur”. Mathematik der Berechnung. 68 (225): 249–260. CiteSeerX 10.1.1.34.1024. doi:10.1090 / S0025-5718-99-00996-5.

    Lesen Sie unbedingt die Errata auch.

  9. ^ ein b Press, William H.; et al. (1992). Numerische Rezepte in Fortran 77: Die Kunst des wissenschaftlichen Rechnens(2. Aufl.). ISBN 978-0-521-43064-7.
  10. ^ Jain, Raj (9. Juli 2010). “Computersystem-Leistungsanalyse Kapitel 26: Zufallszahlengenerierung” (PDF). S. 19–20. Abgerufen 2017-10-31.
  11. ^ Fenerty, Paul (11. September 2006). “Schrages Methode”. Abgerufen 2017-10-31.
  12. ^ Hull, TE; Dobell, AR (Juli 1962). “Zufallszahlengeneratoren” (PDF). SIAM Review . 4 (3): 230–254. doi:10.1137 / 1004061. Abgerufen 2016-06-26.
  13. ^ Severance, Frank (2001). Systemmodellierung und Simulation. John Wiley & Sons, Ltd. 86. ISBN 978-0-471-49694-6.
  14. ^ Austin, David (März 2008). “Zufallszahlen: Nichts dem Zufall überlassen”. Amerikanische Mathematische Gesellschaft.
  15. ^ Implementierung in der Version glibc-2.26. Siehe den Code nach dem Test für “TYPE_0”; die GNU C Bibliothek rand ()In stdlib.h wird nur dann ein einfacher linearer Kongruenzgenerator (Einzelzustand) verwendet, wenn der Zustand als 8 Byte deklariert ist. Wenn der Zustand größer ist (ein Array), wird der Generator zu einem additiven Rückkopplungsgenerator (initialisiert mit minstd_rand0) und die Periode erhöht sich. Siehe die vereinfachter Code das reproduziert die zufällige Sequenz aus dieser Bibliothek.
  16. ^ K. Entacher (21. August 1997). Eine Sammlung ausgewählter Pseudozufallszahlengeneratoren mit linearen Strukturen. CiteSeerX 10.1.1.53.3686. Abgerufen 16. Juni 2012.
  17. ^ “Letzter Entwurf des öffentlichen Ausschusses vom 12. April 2011” (PDF). p. 346f. Abgerufen 21 Dez. 2014.
  18. ^ “Wie Visual Basic Pseudozufallszahlen für die RND-Funktion generiert”. Microsoft-Support . Microsoft. Abgerufen 17. Juni 2011.
  19. ^ Trotz Dokumentation am MSDNRtlUniform verwendet LCG- und nicht Lehmers Algorithmus-Implementierungen, bevor Windows Vista fehlerhaft ist, da das Ergebnis der Multiplikation auf 32 Bit reduziert wird, bevor Modulo angewendet wird
  20. ^ ein b “ISO / IEC 14882: 2011”. ISO. 2. September 2011. Abgerufen 3. September 2011.
  21. ^ GNU Scientific Library: Andere Zufallszahlengeneratoren
  22. ^

    Stephen J. Chapman. “Beispiel 6.4 – Zufallszahlengenerator”.
    “MATLAB-Programmierung für Ingenieure”. 2015. S. 253–256.

  23. ^

    Stephen J. Chapman. “Beispiel 6.4 – Zufallszahlengenerator”.
    “MATLAB-Programmierung mit Anwendungen für Ingenieure”. 2012. S. 292–295.

  24. ^

    SJ Chapman.
    random0. 2004.

  25. ^

    Stephen J. Chapman.
    “Einführung in Fortran 90/95”. 1998. S. 322–324.

  26. ^

    Wu-ting Tsai.
    “‘Modul’: Ein Hauptmerkmal des modernen Fortran”. S. 6–7.

  27. ^ Die Open Group Base-Spezifikationen Ausgabe 7
    IEEE Std 1003.1, Ausgabe 2013
  28. ^ Cadot, Sidney. “rand.s”. cc65. Abgerufen 8. Juli 2016.
  29. ^ O’Neill, Melissa E. (5. September 2014). PCG: Eine Familie einfacher, schneller, platzsparender, statistisch guter Algorithmen zur Erzeugung von Zufallszahlen (PDF) (Technischer Bericht). Harvey Mudd College. S. 6–7. HMC-CS-2014-0905.
  30. ^ Tezuka, Shu; L’Ecuyer, Pierre (Oktober 1993). Zur Gitterstruktur der Zufallszahlengeneratoren Add-with-Carry und Subtrahieren mit Borrow (PDF). Workshop zur stochastischen Numerik. Kyoto Universität.
  31. ^ Tezuka, Shi; L’Ecuyer, Pierre (Dezember 1992). Analyse von Add-with-Carry- und Subtract-with-Borrow-Generatoren (PDF). Tagungsband der Wintersimulationskonferenz 1992. S. 443–447.
  32. ^ Gershenfeld, Neil (1999). “Abschnitt 5.3.2: Lineare Rückkopplung”. Die Natur der mathematischen Modellierung (Erste Ausgabe). Cambridge University Press. p. 59. ISBN 978-0-521-57095-4.
  33. ^ Matsumoto, Makoto; Nishimura, Takuji (Januar 1998). “Mersenne-Twister: ein 623-dimensional gleichverteilter einheitlicher Pseudozufallszahlengenerator” (PDF). ACM-Transaktionen zur Modellierung und Computersimulation. 8 (1): 3–30. CiteSeerX 10.1.1.215.1141. doi:10.1145 / 272991.272995.
  34. ^ Eastlake, Donald E. 3 .; Schiller, Jeffrey I.; Crocker, Steve (Juni 2005). “Traditionelle Pseudozufallssequenzen”. Zufallsanforderungen für die Sicherheit. IETF. sek. 6.1.3. doi:10.17487 / RFC4086. BCP 106. RFC 4086.

Verweise[edit]

Externe Links[edit]

after-content-x4