[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/wiki16\/2021\/01\/04\/linearer-kongruenzgenerator-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/wiki16\/2021\/01\/04\/linearer-kongruenzgenerator-wikipedia\/","headline":"Linearer Kongruenzgenerator – Wikipedia","name":"Linearer Kongruenzgenerator – Wikipedia","description":"before-content-x4 Zwei Modulo-9-LCGs zeigen, wie unterschiedliche Parameter zu unterschiedlichen Zyklusl\u00e4ngen f\u00fchren. Jede Zeile zeigt den Zustand, der sich entwickelt, bis","datePublished":"2021-01-04","dateModified":"2021-01-04","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/wiki16\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/wiki16\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/0\/02\/Linear_congruential_generator_visualisation.svg\/480px-Linear_congruential_generator_visualisation.svg.png","url":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/0\/02\/Linear_congruential_generator_visualisation.svg\/480px-Linear_congruential_generator_visualisation.svg.png","height":"160","width":"480"},"url":"https:\/\/wiki.edu.vn\/wiki16\/2021\/01\/04\/linearer-kongruenzgenerator-wikipedia\/","wordCount":12640,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4  Zwei Modulo-9-LCGs zeigen, wie unterschiedliche Parameter zu unterschiedlichen Zyklusl\u00e4ngen f\u00fchren.  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\u00e4nge 6 erzeugt. Die zweite Reihe ist der gleiche Generator mit einem Startwert von 3, der einen Zyklus der L\u00e4nge 2 erzeugt ein = 4 und c = 1 (untere Reihe) ergibt eine Zyklusl\u00e4nge von 9 mit jedem Samen in [0,\u00a08].EIN linearer Kongruenzgenerator ((LCG) ist ein Algorithmus, der eine Folge von pseudozuf\u00e4lligen Zahlen liefert, die mit einer diskontinuierlichen st\u00fcckweise linearen Gleichung berechnet werden.  Das Verfahren repr\u00e4sentiert einen der \u00e4ltesten 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:  X.n+1=((einX.n+c)modm{ displaystyle X_ {n + 1} =  left (aX_ {n} + c  right) { bmod {m}}}wo X.{ displaystyle X}  ist die Folge von Pseudozufallswerten undm,0X.01{ displaystyle a-1}  ist teilbar durch 4 wenn m{ displaystyle m}  ist teilbar durch 4.Diese drei Anforderungen werden als Hull-Dobell-Theorem bezeichnet.[12][13]Dieses Formular kann mit jedem verwendet werden m , funktioniert aber nur gut f\u00fcr m mit vielen wiederholten Primfaktoren, wie einer Potenz von 2;  Die Verwendung der Wortgr\u00f6\u00dfe eines Computers ist die h\u00e4ufigste Wahl.  Wenn mw\u00e4re eine quadratfreie ganze Zahl, w\u00fcrde dies nur erlauben ein \u2261 1 (mod m ), was ein sehr schlechtes PRNG ergibt;  Eine Auswahl m\u00f6glicher Vollzeitmultiplikatoren ist nur verf\u00fcgbar, 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\u00fcnschenswert f\u00fcr ein – 1 nicht mehr durch Primfaktoren von teilbar sein m als n\u00f6tig.  Also wenn m ist also eine Potenz von 2 ein – 1 sollte durch 4 teilbar sein, aber nicht durch 8 teilbar, dh ein \u2261 5 (Mod 8).[2]::\u00a73.2.1.3In der Tat erzeugen die meisten Multiplikatoren eine Sequenz, die den einen oder anderen Test auf Nicht-Zuf\u00e4lligkeit nicht besteht, und finden einen Multiplikator, der alle anwendbaren Kriterien erf\u00fcllt[2]::\u00a73.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\u00f6chstwertige Bit erreicht die volle Periode.  Wenn eine Pseudozufallszahl kleiner als rist erw\u00fcnscht, \u230arX \/.m\u230b ist ein Ergebnis von viel h\u00f6herer Qualit\u00e4t als X. mod r.  Leider erleichtern die meisten Programmiersprachen das Schreiben von letzteren erheblich (X\u00a0% r), also ist es die am h\u00e4ufigsten 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 \u00fcblicherweise gew\u00e4hlt.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. ::X.n=((X.0((ein– –1)+c)Y.n+X.0=((X.1– –X.0)Y.n+X.0((modm).{ displaystyle X_ {n} = (X_ {0} (a-1) + c) Y_ {n} + X_ {0} = (X_ {1} -X_ {0}) Y_ {n} + X_ {0 } { pmod {m}}.}Im Allgemeinen zwei beliebige Serien X. und Z.  mit dem gleichen Multiplikator und Modul sind durch verbundenX.n– –X.0X.1– –X.0=Y.n=einn– –1ein– –1=Z.n– –Z.0Z.1– –Z.0((modm).{ displaystyle {X_ {n} -X_ {0}  \u00fcber X_ {1} -X_ {0}} = Y_ {n} = {a ^ {n} -1  \u00fcber a-1} = {Z_ {n } -Z_ {0}  \u00fcber Z_ {1} -Z_ {0}} { pmod {m}}.}H\u00e4ufig verwendete Parameter[edit]In der folgenden Tabelle sind die Parameter der h\u00e4ufig verwendeten LCGs aufgef\u00fchrt, einschlie\u00dflich der integrierten rand ()   Funktionen in Laufzeitbibliotheken verschiedener Compiler.  Diese Tabelle soll die Popularit\u00e4t zeigen, keine zu emulierenden Beispiele. Viele dieser Parameter sind schlecht. Tabellen mit guten Parametern sind verf\u00fcgbar.[8][3]QuelleModulmMultiplikatoreinZuwachscAusgangsbits von Seed in rand () oder Zuf\u00e4llig (L)Numerische Rezepte2\u00b3\u00b216645251013904223Borland C \/ C ++2\u00b3\u00b2226954771Bits 30..16 in rand () 30,0 Zoll lrand ()glibc (von GCC verwendet)[15]2\u00b3\u00b9110351524512345Bits 30..0ANSI C: Watcom, Digital Mars, CodeWarrior und IBM VisualAge C \/ C ++ [16]C90, C99, C11: Vorschlag in der ISO \/ IEC 9899,[17]C182\u00b3\u00b9110351524512345Bits 30..16Borland Delphi, virtueller Pascal2\u00b3\u00b21347758131Bits 63..32 von (Samen \u00d7 L)Turbo Pascal2\u00b3\u00b2134775813 (8088405\u2081\u2086)1Microsoft Visual \/ Quick C \/ C ++2\u00b3\u00b2214013 (343FD\u2081\u2086)2531011 (269EC3\u2081\u2086)Bits 30..16Microsoft Visual Basic (6 und fr\u00fcher)[18]2\u00b2\u20741140671485 (43FD43FD\u2081\u2086)12820163 (C39EC3\u2081\u2086)RtlUniform von Native API[19]2\u00b3\u00b9 – 12147483629 (7FFFFFED\u2081\u2086)2147483587 (7FFFFFC3\u2081\u2086)Apple CarbonLib, C ++ 11 minstd_rand0[20]2\u00b3\u00b9 – 1168070siehe MINSTDC ++ 11 minstd_rand[20]2\u00b3\u00b9 – 1482710siehe MINSTDMMIX von Donald Knuth2\u2076\u207463641362238467930051442695040888963407Newlib, Musl2\u2076\u207463641362238467930051Bits 63..32VMS MTH $ ZUF\u00c4LLIG,[21]  alte Versionen von glibc2\u00b3\u00b269069 (10DCD\u2081\u2086)1Javas java.util.Random, POSIX [ln]rand48, glibc [ln]rand48[_r]2\u2074\u207825214903917 (5DEECE66D\u2081\u2086)11Bits 47..16random0[22][23][24][25][26]134456 = 2\u00b37\u2075812128411X.n134456{ displaystyle { frac {X_ {n}} {134456}}}POSIX[27] [jm]rand48, glibc [mj]rand48[_r]2\u2074\u207825214903917 (5DEECE66D\u2081\u2086)11Bits 47..15POSIX [de]rand48, glibc [de]rand48[_r]2\u2074\u207825214903917 (5DEECE66D\u2081\u2086)11Bits 47..0cc65[28]2\u00b2\u00b365793 (10101\u2081\u2086)4282663 (415927\u2081\u2086)Bits 22..8cc652\u00b3\u00b216843009 (1010101\u2081\u2086)826366247 (31415927\u2081\u2086)Bits 31..16Fr\u00fcher \u00fcblich: RANDU [9]2\u00b3\u00b9655390Wie 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\u00f6chstwertigen Bits zur\u00fcck.  Dies liegt daran, dass die Bits h\u00f6herer Ordnung l\u00e4ngere Perioden haben als die Bits niedrigerer Ordnung (siehe unten).  LCGs, die diese K\u00fcrzungstechnik 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 \u00c4ndern der Zufallszahl Mod 2 f\u00fchrt dazu, dass 0 und 1 ohne K\u00fcrzung abwechseln.Vorteile und Nachteile[edit]LCGs sind schnell und ben\u00f6tigen nur minimalen Speicher (ein Modulo-)mZahl, oft 32 oder 64 Bit), um den Status beizubehalten.  Dies macht sie wertvoll f\u00fcr die Simulation mehrerer unabh\u00e4ngiger Streams.  LCGs sind nicht f\u00fcr kryptografische Anwendungen vorgesehen und d\u00fcrfen nicht verwendet werden.  Verwenden Sie f\u00fcr solche Anwendungen einen kryptografisch sicheren Pseudozufallszahlengenerator.  Obwohl LCGs einige spezifische Schw\u00e4chen aufweisen, sind viele ihrer M\u00e4ngel auf einen zu kleinen Zustand zur\u00fcckzuf\u00fchren.  Die Tatsache, dass Menschen seit so vielen Jahren dazu gebracht werden, sie mit so kleinen Modulen zu verwenden, kann als Beweis f\u00fcr die St\u00e4rke der Technik angesehen werden.  Ein LCG mit einem ausreichend gro\u00dfen Zustand kann sogar strenge statistische Tests bestehen.  Ein Modulo-2-LCG, das die hohen 32 Bit zur\u00fcckgibt, besteht die SmallCrush-Suite von TestU01.[citation needed]  und ein 96-Bit-LCG besteht die strengste BigCrush-Suite.[29]F\u00fcr ein bestimmtes Beispiel wird erwartet, dass ein idealer Zufallszahlengenerator mit 32 Bit Ausgabe (nach dem Geburtstagssatz) nachher beginnt, fr\u00fchere Ausgaben zu duplizieren \u221am  \u2248 216 Ergebnisse. Irgendein PRNG, dessen Ausgabe der vollst\u00e4ndige, nicht abgeschnittene Zustand ist, erzeugt erst nach Ablauf des gesamten Zeitraums Duplikate, ein leicht erkennbarer statistischer Fehler.  Aus verwandten Gr\u00fcnden sollte jedes PRNG einen Zeitraum haben, der l\u00e4nger als das Quadrat der Anzahl der erforderlichen Ausg\u00e4nge ist.  Bei modernen Computergeschwindigkeiten bedeutet dies einen Zeitraum von 264 f\u00fcr alle au\u00dfer den am wenigsten anspruchsvollen Anwendungen und l\u00e4nger f\u00fcr anspruchsvolle Simulationen.Ein f\u00fcr LCGs spezifischer Fehler besteht darin, dass bei Auswahl von Punkten in einem n-dimensionalen Raum die Punkte h\u00f6chstens auf liegen. n\u221an! \u22c5m  Hyperebenen (Marsaglias Theorem, entwickelt von George Marsaglia).[5]  Dies ist auf die serielle Korrelation zwischen aufeinanderfolgenden Werten der Sequenz zur\u00fcckzuf\u00fchren X.n.  Unachtsam ausgew\u00e4hlte Multiplikatoren haben normalerweise weit weniger Ebenen mit gro\u00dfem Abstand, was zu Problemen f\u00fchren kann.  Der Spektraltest, bei dem es sich um einen einfachen Test der Qualit\u00e4t eines LCG handelt, misst diesen Abstand und erm\u00f6glicht die Auswahl eines guten Multiplikators.Der Ebenenabstand h\u00e4ngt sowohl vom Modul als auch vom Multiplikator ab.  Ein ausreichend gro\u00dfer Modul kann diesen Abstand unter die Aufl\u00f6sung von Zahlen mit doppelter Genauigkeit reduzieren.  Die Wahl des Multiplikators wird weniger wichtig, wenn der Modul gro\u00df ist.  Es ist immer noch notwendig, den Spektralindex zu berechnen und sicherzustellen, dass der Multiplikator kein schlechter ist, aber rein wahrscheinlich wird es \u00e4u\u00dferst unwahrscheinlich, dass ein schlechter Multiplikator auftritt, wenn der Modul gr\u00f6\u00dfer als etwa 2 ist64.Ein weiterer Fehler, der f\u00fcr LCGs spezifisch ist, ist die kurze Periode der niederwertigen Bits, wenn m wird als Potenz von 2 gew\u00e4hlt. Dies kann durch Verwendung eines Moduls, der gr\u00f6\u00dfer als die erforderliche Ausgabe ist, und unter Verwendung der h\u00f6chstwertigen Bits des Zustands gemindert werden.F\u00fcr einige Anwendungen k\u00f6nnen LCGs jedoch eine gute Option sein.  Beispielsweise ist in einem eingebetteten System die verf\u00fcgbare Speichermenge h\u00e4ufig stark begrenzt.  In \u00e4hnlicher Weise kann in einer Umgebung wie einer Videospielkonsole das Aufnehmen einer kleinen Anzahl von Bits h\u00f6herer Ordnung eines LCG durchaus ausreichen.  (Die niederwertigen Bits von LCGs, wenn m eine Potenz von 2 ist, sollten niemals f\u00fcr irgendeinen Grad an Zuf\u00e4lligkeit 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\u00e4ltig auf ihre Eignung f\u00fcr nicht kryptografische Anwendungen gepr\u00fcft werden, bei denen eine hohe Zuf\u00e4lligkeit von hoher Qualit\u00e4t von entscheidender Bedeutung ist.  F\u00fcr Monte-Carlo-Simulationen muss ein LCG einen Modul verwenden, der gr\u00f6\u00dfer und vorzugsweise viel gr\u00f6\u00dfer als der W\u00fcrfel der Anzahl der erforderlichen Zufallsstichproben ist.  Dies bedeutet zum Beispiel, dass ein (gutes) 32-Bit-LCG verwendet werden kann, um ungef\u00e4hr tausend Zufallszahlen zu erhalten;  Ein 64-Bit-LCG ist gut f\u00fcr ungef\u00e4hr 221 Zufallsstichproben (etwas mehr als zwei Millionen) usw. Aus diesem Grund sind LCGs in der Praxis nicht f\u00fcr gro\u00df angelegte Monte-Carlo-Simulationen geeignet.Beispiel f\u00fcr 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 seedBeispiel f\u00fcr einen kostenlosen Pascal-Code[edit]Free Pascal verwendet einen Mersenne Twister als Standard-Pseudozufallszahlengenerator, w\u00e4hrend 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}interfacefunction LCGRandom: extended; overload;inline;function LCGRandom(const range:longint):longint;overload;inline;implementationfunction 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 \u00e4ndern, wenn sie eine neue Nummer generiert.  Mehrere Threads k\u00f6nnen gleichzeitig auf diesen Status zugreifen, was zu einer Racebedingung f\u00fchrt.  Implementierungen sollten unterschiedliche Status mit jeweils eindeutiger Initialisierung f\u00fcr unterschiedliche Threads verwenden, um gleiche Folgen von Zufallszahlen bei gleichzeitiger Ausf\u00fchrung von Threads zu vermeiden.LCG-Derivate[edit]Es gibt mehrere Generatoren, die lineare Kongruenzgeneratoren in unterschiedlicher Form sind, und daher k\u00f6nnen die zur Analyse von LCGs verwendeten Techniken auf sie angewendet werden.Ein Verfahren zum Erzeugen eines l\u00e4ngeren Zeitraums besteht darin, die Ausgaben mehrerer LCGs verschiedener Zeitr\u00e4ume mit einem gro\u00dfen kleinsten gemeinsamen Vielfachen zu summieren;  Der Wichmann-Hill-Generator ist ein Beispiel f\u00fcr diese Form.  (Wir w\u00fcrden es vorziehen, wenn sie vollst\u00e4ndig koprime sind, aber ein Primmodul impliziert eine gerade Periode, daher muss mindestens ein gemeinsamer Faktor 2 vorhanden sein.) Dies kann als \u00e4quivalent 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\u00f6\u00dfe von b = 2w  und hinkt r und s((r > s) entsprechen LCGs mit einem Modul von br \u00b1 bs \u00b1 1.[30][31]Multiplizieren Sie mit Carry-PRNGs mit einem Multiplikator von ein sind \u00e4quivalent zu LCGs mit einem gro\u00dfen Primmodul von abr\u22121 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\u00fcckkopplungsschieberegisterkonstruktion, die auf der Arithmetik in GF basiert (2).[x]der Polynomring \u00fcber GF (2).  Anstelle einer ganzzahligen Addition und Multiplikation sind die Grundoperationen eine Exklusiv- oder \u00dcbertrag-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\u00e4che der niederwertigen Bits, die das arithmetische Modulo 2 plagenk.[32]Beispiele f\u00fcr diese Familie sind Xorshift-Generatoren und der Mersenne-Twister.  Letzteres bietet einen sehr langen Zeitraum (219937\u22121) und variieren die Gleichm\u00e4\u00dfigkeit, aber es bestehen einige statistische Tests nicht.[33]Verz\u00f6gerte 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\u00fcckkopplungsschieberegisters mit geeigneten Tests zu erfassen[34]  wie der in der TestU01-Suite implementierte lineare Komplexit\u00e4tstest;  Eine aus aufeinanderfolgenden Bits eines LFSR initialisierte boolesche zirkulierende Matrix hat niemals einen h\u00f6heren Rang als den Grad des Polynoms.  Das Hinzuf\u00fcgen einer nichtlinearen Ausgangsmischfunktion (wie bei den Konstruktionen xoshiro256 ** und permutierter kongruenter Generatoren) kann die Leistung bei statistischen Tests erheblich verbessern.Eine weitere Struktur f\u00fcr ein PRNG ist eine sehr einfache Wiederholungsfunktion in Kombination mit einer leistungsstarken Ausgangsmischfunktion.  Dies umfasst Blockchiffren im Z\u00e4hlermodus und nicht kryptografische Generatoren wie z SplitMix64.Eine Struktur \u00e4hnlich wie LCGs, aber nicht\u00e4quivalent ist der mehrfach rekursive Generator: X.n = (ein1X.n\u22121 + ein2X.n \u22122 + \u00b7\u00b7\u00b7 + einkX.n – –k) mod mzum k\u2265 2. Mit einem Primzahlmodul k\u00f6nnen Perioden bis zu erzeugt werden mk\u22121, also eine n\u00fctzliche Erweiterung der LCG-Struktur auf gr\u00f6\u00dfere Zeitr\u00e4ume.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]^ “”Lineare Kongruenzgeneratoren“von Joe Bolte, Wolfram Demonstrationsprojekt.^ 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\u201326.^ ein b c Steele, Guy;  Vigna, Sebastiano (15. Januar 2020).  “Rechenlich einfache, spektral gute Multiplikatoren f\u00fcr 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\u00f6rige Daten bei https:\/\/github.com\/vigna\/CPRNG.^ 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.^ ein b Marsaglia, George (September 1968). “Zufallszahlen fallen haupts\u00e4chlich in die Flugzeuge” (PDF). PNAS. 61 (1): 25\u201328.  Bibcode:1968PNAS … 61 … 25M.  doi:10.1073 \/ pnas.61.1.25.  PMC 285899.  PMID 16591687.^ Park, Stephen K.;  Miller, Keith W. (Oktober 1988). “Zufallszahlengeneratoren: Gute sind schwer zu finden” (PDF). Mitteilungen der ACM. 31 (10): 1192\u20131201.  doi:10.1145 \/ 63039.63042.^ H\u00f6rmann, Wolfgang;  Derflinger, Gerhard (1993). “Ein tragbarer einheitlicher Zufallszahlengenerator, der f\u00fcr die Ablehnungsmethode gut geeignet ist” (PDF). ACM-Transaktionen mit mathematischer Software . 19 (4): 489\u2013495.  CiteSeerX 10.1.1.52.3811.  doi:10.1145 \/ 168173.168414. ein Multiplikator ungef\u00e4hr so \u200b\u200bklein wie \u221amerzeugt Zufallszahlen mit einer schlechten eindimensionalen Verteilung.^ ein b L’Ecuyer, Pierre (1999). “Tabellen linearer Kongruenzgeneratoren unterschiedlicher Gr\u00f6\u00dfe und guter Gitterstruktur”. Mathematik der Berechnung. 68 (225): 249\u2013260.  CiteSeerX 10.1.1.34.1024.  doi:10.1090 \/ S0025-5718-99-00996-5. Lesen Sie unbedingt die Errata auch.^ 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.^ Jain, Raj (9. Juli 2010). “Computersystem-Leistungsanalyse Kapitel 26: Zufallszahlengenerierung” (PDF).  S. 19\u201320.  Abgerufen 2017-10-31.^ Fenerty, Paul (11. September 2006). “Schrages Methode”.  Abgerufen 2017-10-31.^ Hull, TE;  Dobell, AR (Juli 1962). “Zufallszahlengeneratoren” (PDF). SIAM Review . 4 (3): 230\u2013254.  doi:10.1137 \/ 1004061.  Abgerufen 2016-06-26.^ Severance, Frank (2001). Systemmodellierung und Simulation.  John Wiley & Sons, Ltd.  86. ISBN 978-0-471-49694-6.^ Austin, David (M\u00e4rz 2008). “Zufallszahlen: Nichts dem Zufall \u00fcberlassen”.  Amerikanische Mathematische Gesellschaft.^ Implementierung in der Version glibc-2.26. Siehe den Code nach dem Test f\u00fcr “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\u00f6\u00dfer ist (ein Array), wird der Generator zu einem additiven R\u00fcckkopplungsgenerator (initialisiert mit minstd_rand0) und die Periode erh\u00f6ht sich.  Siehe die vereinfachter Code das reproduziert die zuf\u00e4llige Sequenz aus dieser Bibliothek.^ K. Entacher (21. August 1997). Eine Sammlung ausgew\u00e4hlter Pseudozufallszahlengeneratoren mit linearen Strukturen.  CiteSeerX 10.1.1.53.3686.  Abgerufen 16. Juni 2012.^ “Letzter Entwurf des \u00f6ffentlichen Ausschusses vom 12. April 2011” (PDF).  p.  346f.  Abgerufen 21 Dez. 2014.^ “Wie Visual Basic Pseudozufallszahlen f\u00fcr die RND-Funktion generiert”. Microsoft-Support .  Microsoft.  Abgerufen 17. Juni 2011.^ 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^ ein b “ISO \/ IEC 14882: 2011”.  ISO.  2. September 2011.  Abgerufen 3. September 2011.^ GNU Scientific Library: Andere Zufallszahlengeneratoren^ Stephen J. Chapman.  “Beispiel 6.4 – Zufallszahlengenerator”.“MATLAB-Programmierung f\u00fcr Ingenieure”.  2015. S. 253\u2013256.^ Stephen J. Chapman.  “Beispiel 6.4 – Zufallszahlengenerator”.“MATLAB-Programmierung mit Anwendungen f\u00fcr Ingenieure”.  2012. S. 292\u2013295.^ SJ Chapman.random0.  2004.^ Stephen J. Chapman.“Einf\u00fchrung in Fortran 90\/95”.  1998. S. 322\u2013324.^ Wu-ting Tsai.“‘Modul’: Ein Hauptmerkmal des modernen Fortran”.  S. 6\u20137.^ Die Open Group Base-Spezifikationen Ausgabe 7IEEE Std 1003.1, Ausgabe 2013^ Cadot, Sidney. “rand.s”. cc65.  Abgerufen 8. Juli 2016.^ 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\u20137.  HMC-CS-2014-0905.^ 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\u00e4t.^ Tezuka, Shi;  L’Ecuyer, Pierre (Dezember 1992). Analyse von Add-with-Carry- und Subtract-with-Borrow-Generatoren (PDF).  Tagungsband der Wintersimulationskonferenz 1992.  S. 443\u2013447.^ Gershenfeld, Neil (1999).  “Abschnitt 5.3.2: Lineare R\u00fcckkopplung”. Die Natur der mathematischen Modellierung  (Erste Ausgabe).  Cambridge University Press.  p. 59.  ISBN 978-0-521-57095-4.^ Matsumoto, Makoto;  Nishimura, Takuji (Januar 1998). “Mersenne-Twister: ein 623-dimensional gleichverteilter einheitlicher Pseudozufallszahlengenerator” (PDF). ACM-Transaktionen zur Modellierung und Computersimulation. 8 (1): 3\u201330.  CiteSeerX 10.1.1.215.1141.  doi:10.1145 \/ 272991.272995.^ Eastlake, Donald E. 3 .;  Schiller, Jeffrey I.;  Crocker, Steve (Juni 2005). “Traditionelle Pseudozufallssequenzen”. Zufallsanforderungen f\u00fcr die Sicherheit.  IETF.  sek.  6.1.3.  doi:10.17487 \/ RFC4086.  BCP 106. RFC 4086.Verweise[edit]Dr\u00fccken Sie, WH;  Teukolsky, SA;  Vetterling, WT;  Flannery, BP (2007), “Abschnitt 7.1.1. Etwas Geschichte”, Numerische Rezepte: Die Kunst des wissenschaftlichen Rechnens(3. Aufl.), New York: Cambridge University Press, ISBN 978-0-521-88068-8Gentle, James E. (2003). Zufallszahlengenerierung und Monte-Carlo-Methoden, 2. Auflage, Springer, ISBN 0-387-00178-6.Joan Boyar (1989). “Ableiten von Sequenzen, die von Pseudozufallszahlengeneratoren erzeugt werden” (PDF). Zeitschrift der ACM. 36 (1): 129\u2013141.  doi:10.1145 \/ 58562.59305.  (In diesem Artikel werden effiziente Algorithmen zum Ableiten von Sequenzen angegeben, die von bestimmten Pseudozufallszahlengeneratoren erzeugt werden.)Externe Links[edit]Die Simulation Linearer Kongruenzgenerator visualisiert die Korrelationen zwischen den Pseudozufallszahlen bei der Manipulation der Parameter.Sicherheit der Zufallszahlengenerierung: Eine kommentierte BibliographieLinear Congruential Generators posten auf sci.mathDas Computerkunstprojekt “Death of Art” bei Goldstein Technologies LLC verwendet eine LCG, um 33.554.432 Bilder zu generierenP. L’Ecuyer und R. Simard, “TestU01: AC-Bibliothek zum empirischen Testen von Zufallszahlengeneratoren”, Mai 2006, \u00fcberarbeitet November 2006, ACM-Transaktionen mit mathematischer Software, 33, 4, Artikel 22, August 2007.Artikel \u00fcber eine andere Art, LCG zu knacken     (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki16\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki16\/2021\/01\/04\/linearer-kongruenzgenerator-wikipedia\/#breadcrumbitem","name":"Linearer Kongruenzgenerator – Wikipedia"}}]}]