Diskussion:Kongruenzgenerator

Bezeichnungen

Die Bezeichnungen sind m.E. völlig falsch. Ein linearer Kongruenzgenerator sollte von der Form

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y_i = (\sum_{k=1}^{n} a_k y_{i-k} + b) \ \bmod \ m }

sein, denn hier gehen alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y_i} linear ein. Ein allgemeiner Kongruenzgenerator hingegen würde auch Produkte und Potenzen der $y_{i}$ einschließen.

Und warum heißen sie rekursive arithmetische Zufallszahlengeneratoren? Was hier gemacht wird, ist doch Iteration und nicht Rekursion: die gleiche Berechnungsvorschrift wird immer wieder auf den aktuellen Zustand des Generators angewandt, um daraus den nächsten Zustand (und eine Scheinzufallszahl) zu berechnen. --Megatherium 11:02, 23. Feb. 2007 (CET)

Zuerst einaml vielen Dank für deine Arbeit. Als ich den Artikel bearbeitete habe ich den Knuth als Quelle genommen. Vielleicht gibt es ja auch ein anderes Standardwerk, allerdings kenne ich mich in dem Bereich nicht wirklich aus. --Stefan Birkner 12:20, 23. Feb. 2007 (CET)

a) Die Bezeichnung im Artikel ist nicht willkürlich, sondern folgt den Standardbezeichnungen in der einschlägigen Literatur, auch wenn diese vlt. nicht immer intuitiv ist. b) Rekursiv deshalb, weil Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y_i} von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y_{i-1},...,y_{i-k}} abhängt. Will man jetzt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y_{100}} berechnen, muss man die Abhängigkeiten auflösen, und rekursiv bis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y_0} alle anderen Folgenglieder berechnen (auch wenn sich viele der Generatoren auf eine explizite Darstellung bringen lassen, um die Rekursion hinfällig zu machen).--Etamatic123 (Diskussion) 14:55, 30. Apr. 2012 (CEST)

Warum ist es vorteilhaft beim linearen Kongruenzgenerator für m eine Zweierpotenz zu wählen?

Es wird im Artikel angedeutet, dass man das machen kann. Mir wird aber nicht klar, warum das vorteilhaft ist. --source 19:21, 10. Nov. 2007 (CET)

Dabei geht es nur darum, dass die Berechnung möglichst schnell gehen soll. Bei Zweierpotenzen kann man schnellere Prozessorbefehle nehmen, die bitweise arbeiten. --MAF-Soft 11:28, 11. Jun. 2010 (CEST)

Stimmt genau - für Zweierpotenzen als Modul erspart man sich die modulare Reduktion nach jedem Schritt. Wenn der Modul 2^k ist, kann man einfach alles links der k-ten Stelle wegstreichen, und muss nichts wirklich berechnen.--Etamatic123 (Diskussion) 14:52, 30. Apr. 2012 (CEST)

Zufallsgeneratoren

Hallo, ich glaube, hier geht etwas mit den Bezeichnungen und Zuordnungen für Zufallsgeneratoren durcheinander, weshalb es auch zu Problemen mit der inhaltlich strukturellen Gliederung von Zufallsgeneratoren kommt. Ich schlage deshalb folgende inhaltliche Neugliederung bzw. Erweiterungen vor und begründe dabei auch kurz weshalb. Da meine hoffentlich konstruktiven Verbesserungsvorschläge viele Seiten zum Thema Zufallsgeneratoren betreffen, sollte dieser Diskussions-Artikel evtl an eine "zentralere" Stelle verschoben werden, wenn es denn eine solche gibt. Die von mir verwendeten Begriffe gibt es zum Teil schon 40 Jahre und länger, also bevor die meisten heutigen Internetbenutzer geboren wurden, tauchen aber in der deutschen Wikipedia bisher zum Teil gar nicht auf (wie "Mehrfach rekursive Zufallsgeneratoren" - MRG), dafür gibt es hier völlig neu eingeführte Begriffe wie "Rekursiver arithmetischer Zufallsgenerator", die mir bisher unbekannt waren und die ich so nicht in (meinen) Büchern gefunden habe.

Alle diese Untergliederungen sollten jeweils einem seperaten Artikel entsprechen, damit sie a) wirklich unter ihrem Namen auch erreichbar sind und die Links nicht künstlich "umgebogen" werden müssen wie bei den Fibonacci-Generatoren, b) keine weiteren rekursiven Untergliederungen mit diversen Überschriftformaten innerhalb des jeweiligen Artikels nötig sind, wie in diesem Beitrag hier und c) die einzelnen Artikel damit wesentlich kürzer und somit übersichtlicher werden. Inhaltlich übergeordnete Artikel sollten per Link auf die ihnen untergeordneten verweisen und umgekehrt, damit man alle Informationen zum Thema Zufallsgeneratoren schnell, systematisch und immer findet und nicht nur per Zufall oder erst nach langem Suchen wiederfindet. Mein langer mehrfach rekursiv gegliederter Diskusions-Artikel hier ist also das ultimative Gegenbeispiel.

Kombination von Zufallsgeneratoren

Um die diversen Mängel einzelner konkreter Zufallsgeneratoren so gut wie möglich abzustellen, kombiniert man mehrere (N > 1) verschiedene einfache, kleine, schnelle, kostengünstige Zufallsgeneratoren zu einem neuen größeren, komplexeren, sicheren, aber meist langsameren Zufallsgenerator.

Hybride Zufallsgeneratoren

Eine Kombination aus mindestens einem meist langsamen nichtdeterministischen und mindestens einem meist wesentlich schnelleren deterministischen Zufallsgenerator (z.B. die nichtdeterministische Initialisierung von deterministischen Zufallsgeneratoren).

Multiplexer

Ein steuernder Zufallsgenerator bestimmt, welche Ausgaben der (N > 1) "parallel geschalteten" Zufallsgeneratoren einer Gruppe zu einer einzigen "multiplexten" Ausgabe zusammengemixt werden.

Stop-And-Go Generatoren

Ein steuernder Zufallsgenerator bestimmt, welcher der (N > 1) "parallel geschalteten" Zufallsgeneratoren einer Gruppe einen Schritt macht (Go) und dessen Ausgabe quasi freigeschalten wird. Alle anderen Zufallsgeneratoren dieser Gruppe werden nicht getaktet (Stop).

Kaskaden

Reihenschaltung von (N > 1) LFSR's etc. Der Ausgang des vorherigen LFSR's bestimmt, ob das nachfolgende LFSR einen Schritt macht oder nicht. Also N-1 Zufallsgeneratoren nur zur Steuerung, die Ausgabe kommt allein vom Ausgang des letzten LFSR's.

Nichtdeterministische Zufallsgeneratoren

Also alle physikalischen, echten Zufallsgeneratoren, meist langsam mit schlechten statistischen Eigenschaften aber dafür schwer oder gar nicht vorhersagbar ...

diverse Systemuhren, Zähler

Ziemlich langsame, oft nur alle 250 oder gar nur alle 500 Millisekunden getaktete bzw. aktualisierte Zähler, Uhren, keine Nutzereingabe erforderlich.

User-Input-Devices (Keybord, Mouse, ...)

Auswertung der Zeit in Millisekunden zwischen Tatstauranschlägen, Mausbewegungen, Verwendung des ASCII-Wertes der gedrückten Taste, der Pixelkoordinaten der Maus etc. Nutzereingabe unbedingt erforderlich. Deswegen noch viel langsamer als Systemuhren.

Deterministische Zufallsgeneratoren

Deterministische (also Pseudo-) Zufallsgeneratoren gliedern sich meines Erachtens nach in zwei Hauptgruppen auf, nämlich in "Nichtrekursive Zufallsgeneratoren" und "Rekursive Zufallsgeneratoren". Fakt ist weiterhin, rekursive und nicht rekursive Zufallsgenaroren lassen sich häufig ineinander umwandeln. Aber dann läßt sich meist eine von beiden Bildungsvorschriften wesentlich effizienter und schneller berechnen als die andere und danach erfolgt dann auch die inhaltliche Zuordung der Zufallsgeneratoren zu diesen beiden Hauptgruppen.

Nichtrekursive Zufallsgeneratoren

Nichtrekursive Zufallsgeneratoren ermitteln den nächsten Zufallswert $x_{i}$ mit Hilfe einer expliziten Formel, die nur vom Index Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} abhängt, also Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_i = f(i)} . Es werden $(k=0)$ also keinerlei quasizufällige Initialwerte benötigt und auch keine schon berechneten Zufallswerte aufgehoben, um daraus die nächsten Zufallswerte zu berechnen.

Lineare nichtrekursive Zufallsgeneratoren

Hierunter fallen alle formelbasierten Modulorechnungen der Form Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_i = (a * i + b)\ mod\ m} , mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (a,b,m)} konstant, welche zum Teil sehr langen Perioden aber dafür oft eine sehr leichte Vorhersagbarkeit (oft mit linearer Komplexität) haben. Hierher gehören meines Erachtens auch die "arithmetischen Zufallsgeneratoren", die alle oder eine gewisse Menge von Nachkommastellen von (linearen) Vielfachen einer irrationalen Zahl a = (Pi, e, sqrt(2), ...) als i-ten Zufallswert ausgeben, dann wäre b = 0 und m = 1.

Nichtlineare nichtrekursive Zufallsgeneratoren

Das sind z.B. alle expliziten LookUpTable-Verfahren der Form Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_i = lookUpTable[i]} , die meist eine wesentlich schwierigere Vorhersagbarkeit (oft mit nichtlinearer Komplexität), dafür aber meist eine kleine Periode haben, da man die komplette Zuordnung Index <==> Zufallswert ja explizit in der Tabelle speichern muss.

Rekursive Zufallsgeneratoren

Rekursive Zufallsgeneratoren, welche zur Berechnung des nächsten Zufallswert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_i} auf (k > 0) also wenigstens einen oder gar mehrere bereits berechnete oder vorinitialisierte Werte zugreifen, also Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_i = f(x} _i-1Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle , x} _i-2Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle , ... , x} _i-kFehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle )\ mod \ m} , gliedern sich auf in "einfach rekursive Zufallsgeneratoren" und in "mehrfach rekursive Zufallsgeneratoren".

Einfach rekursive Zufallsgeneratoren (k = 1) oder allgemeine Kongruenzgeneratoren

Einfach rekursive Zufallsgeneratoren, oft auch als Kongruenzgeneratoren bezeichnet, greifen zur Berechnung des nächsten Zufallswertes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_i} auf genau einen bereits berechneten oder vorinitialisierten Wert zu, also $x_{i}=(a*x$_i-1ⁿFehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle + b)\ mod \ m} .

Lineare Kongruenzgenaroren (n = 1)

Meist schnell berechenbare aber dafür leicht vorhersagbare Kongruenzgenaroren mit (n = 1) , also der Form Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_i = (a * x} _i-1Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle + b)\ mod \ m} . Maximal mögliche Periode = m.

= Additive lineare Kongruenzgeneratoren (a = 1, b # 0) =

Na so was, habe ich hier tatsächlich schon die maximal mögliche Verschachtelungstiefe überschritten? Also auch das Internet hat seine Grenzen! Maximal mögliche Periode = m.

= Multiplikative lineare Kongruenzgeneratoren (a > 1, b = 0) =

Na so was, habe ich hier tatsächlich schon die maximal mögliche Verschachtelungstiefe überschritten? Also auch das Internet hat seine Grenzen! Maximal mögliche Periode = (m - 1).

Nichtlineare Kongruenzgenaroren (n > 1)

Oft langsamere aber dafür wesentlich schwerer vorhersagbare Kongruenzgeneratoren mit (n > 1), wie Blum-Blum-Shub mit (n = 2), alle Arten von Inversen Kongruenzgeneratoren mit (n = -1 mod m), etc.

Mehrfach rekursive Zufallsgeneratoren (k > 1)

Mehrfach rekursive Zufallsgeneratoren greifen zur Berechnung des nächsten Zufallswertes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_i} auf mehrere bereits berechnete oder vorinitialisierte Werte zu, verzichtet aber aus Geschwindigkeitsgründen meist auf alle nichtlineare Potenzen mit (n > 1), so dass man meist folgende Formel hat: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_i = (Sum(a_j * x} _i-jFehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle ) + b) \ mod \ m} für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j = (1,...,k)} . Meistens verzichtet man sogar noch auf die Multiplikation völlig, in dem man alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_j = \{0,1\}} wählt.

Fibonacci LFSR's (k = 2,4)

N Bit lange LFSR's mit primitivem Polynom vom Grad N über Z₂ um die maximale Periodenlänge von (2^N-1) zu erreichen. Bei Trinomen muß auf (k = 2) gespeicherte Bits sonst auf mindestens (k = 4) gespeicherte Bits zugegriffen werden. Jedes primitive Fibonacci-Polynom läßt sich immer in sein (gespiegeltes) ebenfalls primitives Galoise-Polynom vom selben Grad umwandeln. Dann ist die Berechnung des neuen Bits einfacher und schneller, man sieht dann aber nicht mehr die mehrfache Rekusrsivität.

Nicht verzögerte Fibonacci-Generatoren (k = 2)

Niederwertigste Bits entsprechem einem (N = 2) Bit langen Fibonacci-LFSR der Periode 3, die jeweils um (M-1) Bit erweitert wurden. Maximal mögliche Gesamtperiode 3 * 2^(M-1). Das zugehörige primitive Polynom über Z₂ vom Grad 2 ist immer das Trinom (x² + x + 1).

Verzögerte Fibonacci-Generatoren (k = 2,4)

die eigentlich nichts weiter als eine (M-1)-Bit-Erweiterung eines (N > 2) Bit langen Fibonacci-LFSR's darstellen. Maximal mögliche Gesamtperiode (2^N - 1) * 2^(M-1). Wenn das zugehörige primitive Polynom ein Trinom ist, muß man auf genau (k = 2) aus N gespeicherte Werte zurückgreifen, sonst mindestens auf (k = 4) aus N.

RC4 (k = 2)

Hier werden pro Aufruf die zwei gespeicherte Werte, auf die zur Brechnung des nächsten Zufallswertes zugegriffen wird, zusätzlich noch vertauscht. Sehr schnell, sehr sicher, gute statistische Eigenschaften, lange Periode, ...

MultiplyWithCarry-Generatoren (k = 2)

Hier wird bei jedem Aufruf auf genau zwei von insgesamt (r >= k) gespeicherten Werte zugegriffen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (carry} _i-1Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle , x} _i-r+1Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle )} und eigentlich ein neues Doppelwort Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (carry_i, x_i)} berechnet und aufgehoben, wovon aber nur die untere, niederwertige Hälfte, das Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_i} als nächster Zufallswert ausgegeben wird. Einer der wenigen mehrfach rekursiven Zufallsgeneratoren mit (a > 1), aber trotzdem schnell.

...

--Aragorn321 (Diskussion) 14:42, 6. Jan. 2013 (CET)

Mehrstellige schnelle und gute lineare Kongruenzgeneratoren mit einer Zweierpotenz als Modul

Der Hauptmangel, über den alle gemischten linearen Kongruenzgeneratoren mit einem Modul M = 2^N verfügen, liegt in der Tatsache begründet, dass das durch die numerische Addition zweier ungerader Zahlen auf der niedrigsten Bitposition (also Bit1 oder LSB) erzeugte Überlauf- oder Carry-Bit genau jeden zweiten Takt entsteht, und dann mit jeweils halbierter Taktrate sukzessive nach links zu den höherwertigen Bits durchgereicht wird, womit jedes LSB einer durch einen gemischten lineraren Kongruenzgenerators erzeugten Zufallsfolge X mit x_i = a * x_i-1 + b, wie im Artikel bereits erwähnt, leider nur die Periode p₁ = 2¹ hat. Es wird also eine gerader Zufallswert erzeugt, der beim nächsten Mal durch Addition des stets ungeraden Wertes b wieder zu einem ungeraden Zufallswert wird, womit das Spiel wieder von vorn anfängt. Diese Carry-Bit-Wanderung hat zur Konsequenz, dass jedes Bit i eines auf obige Weise erzeugten Zufallswertes leider immer nur die Periode p_i = 2ⁱ hat, was auch für jeden n <= N Bit langen Teilwert zutrifft, wenn man nur die n niederwertigsten Bits dafür verwendet. Also nur dann, wenn das oberste Bit (BitN oder MSB) im Zufallswert mit enthalten ist, hat dieser auch die maximale Periode p des gesamten Zufallsgenerators von p_N = 2^N. Um sich diesen Umstand besser zu veranschaulichen, sollte man einen solchen Zufallsgenerator einfach binären betrachten, dass heißt jeden erzeugten Zufallswert z.B. als Folge von N=4 Bits betrachten, sowie a=1, b=1 und den Startwert x₀=0 wählen. Dann erhält man folgende "Zufallssequenz" (siehe Spalte 2)

i	xi (a=1, b=1)	xi (a=9, b=5)
0	0000	0000
1	0001	0101
2	0010	0010
3	0011	0111
...	....	....
15	1111	0011
16	0000	0000
17	0001	0101

Es werden also alle möglichen 2⁴=16 Werte eines Halbbytes (N=4 Bit) erzeugt. Ändert man die Parameter des Zufallsgenerators z.B. auf a=9 und b=5 (Spalte 3), erhält man zwar wiederum alle 16 Werte aber diesmal trotz gleichen Startwertes in einer anderen Reihenfolge. Eine Veränderung des Startwertes ohne Veränderung der Parameter a und b bewirkt dagegen keine Veränderung der Reihenfolge der Zufallswertsequenz, sondern nur eine einfache Verschiebung derselben Sequenz auf den neuen Startwert.

Wegen dieser schlechten Qualität der von linearen Kongruenzgeneratoren erzeugten Zufallswerte, wird in der Praxis fast immer der von linearen Kongruenzgeneratoren erzeugte Zufallswert x_i speziell für die Ausgabe mit einer sogenannten Ausgabefunktion f noch extra modifiziert bzw. verändert y_i = f(x_i). Abgespeichert zur weiteren Verwendung wird dagegen der noch nicht modifizierte Zufallswert x_i. Eine beliebte weil einfache und schnelle Methode ist, man erzeugt einfach mehr Bits als benötigt werden und gibt nur die gewünschte Anzahl an höherwertigen Bits zurück. Java verwendet z.B. (in der amerikanischen Exportversion) einen solchen 48 Bit langen gemischten linearen Kongruenzgenerator und gibt als 32 Bit langen Zufallswert nur die höherwertigen, also oberen 32 Bits zurück (Bit48, ..., Bit17), womit natürlich auch die Periode des LSB des zurückgegebenen Teilwertes p₁₇=2¹⁷ und des gesamten 32 Bit langen Teilwertes p₄₈=2⁴⁸ ist. Selbstverständlich kann man diese Export-Beschränkung auf 48 Bit legal umgehen, in dem man einen "selbsgestrickten" gemischten linearen Zufallsgenerator der Länge N=64 verwendet und ebenfalls nur die oberen 32 Bit zurückgibt, oder diese vorher auf die unteren 32 Bit per XOR aufaddiert und dann das 32 Bit lange XOR-Ergebnis zurückgibt, was eine LSB-Periode von p₃₃=2³³ und eine MSB-Periode von p₆₄=2⁶⁴ergeben würde. Selbst das dürfte aber für die meisten heutige Belange absolut unzureichend sein.

(Fakt 1) Werden zwei Bits i und j mit (i < j) und somit zwangsweise unterschiedlichen Perioden p_i=2ⁱ < p_j=2^j per XOR addiert, beträgt die Periode des Ergebnisbits p_i xor p_j = lcm(p_i,p_j) = max(p_i,p_j) = p_j. Man kann also niederwertige Bits eines gemischten linearen Zufallsgenerators ganz einfach aufwerten oder "veredeln", in dem man höherwertige Bits per XOR aufaddiert.

(Fakt 2) Wenn man die K <= N/2 höchstwertigen Bits auf beliebige andere K niederwertige Bits per XOR aufaddiert erhält man jeweils K Bit lange Teilwerte mit maximaler Periode p=2^N, wovon jeder der 2^K möglichen Werte genau 2^N-K mal erzeugt wird, was einer absolut idealen Gleichverteilung entspricht.

(Fakt 3) Das allgemeine Funktionsprinzip (die Mathematik) von gemischten linearen Kongruenzgeneratoren mit einer Zweierpotenz als Modul M=2^N, ist definitiv nicht auf einstellige Werte (z.B. ein Maschinenwort) der Länge N beschränkt, auch wenn dies der in der Praxis nahezu ausschließlich vorkommende Fall ist, da jede "einstellige" Multiplikation in der Regel in genau einem CPU-Takt ausgeführt werden kann und somit "einstellige" lineare Kongruenzgeneratoren sehr schnell sind.

(Fakt 4) Verkettet man mehrere Zellen mit jeweils K<=N/2 Bits (also maximal der halben Maschinenwortlänge, da die bei der Multiplikation von zwei K-Bit langen Werten entstehenden maximal K Carrybits C auch noch in das Maschinenwort passen müssen) zu einem L stelligen Vektor und geht damit zwangsweise von einer "einstelligen" zu einer Vektormultiplikation über, kann man zwar K*L Bit lange Zufallswerte mit sehr großer Periode p=2^K*L erzeugen, würde dafür aber wegen der Vektormultiplikation einen quadratisch wachsenden Zeitaufwand von O(L²) in Kauf nehmen müssen, was in der Regel nicht akzeptiert wird.

(Fakt 5) Verwendet man zwar einen L-stelligen Zufallswert X=[x₁,x₂,...,x_L](mit jeweils K Bits pro Zelle) aber nur einen einstelligen Faktor A (mit K Bit), bleibt zum einen die schöne lange Periode p=2^K*L erhalten und zum zweiten reduziert sich die benötigte Zeit hierfür von einem quadratischen auf ein linearen Aufwand O(L¹). Der additive Offset B=[b₁,b₂,...,b_L] kann dabei L-stellig bleiben, da die Vektoraddition nur ein lineares Zeitverhalten O(L¹) aufweist.

(Fakt 6) Da man wegen der geringen Zufallsqualität der niederwertigen Bits sowieso nicht die gesamten K*L Bit langen Zufallswerte verwenden kann, in jedem der L Multiplikationsschritte aber 2*K neue Zufallsbits anfallen (c += a * x_i + b_i), kann man die niederwertigen K Bits von c (das neue x_i) jeweils mit den höchstwertigen K Bits des L-stelligen Zufallsvektors x₁ "veredeln" und zurückgeben. Somit erhält man bereits nach jedem der L Schritte einen jeweils K Bit langen Zufallswert, der Dank der "Veredelung" stets die maximale Periode des gesamten Zufallsgenerators hat, welche sich sogar durch die Salamischeibentaktik um den Faktor L auf p=L*2^K*Lvergrößert. Ist L selbst wiederum eine Zweierpotenz L=(2,4,8,16,32,64, ...), so ist die resultiernde Gesamtperiode des mehrstelligen linearen Kongruenzgenerators immer noch eine Zweierpotenz, andernfalls allerdings nicht mehr.

Auf diesem Wege lassen sich also gemischte lineare Kongruenzgeneratoren mit im Prinzip beliebig langer Periode p=L*2^K*L erzeugen, die definitiv nicht über die oben beschriebenen Qualitätsprobleme der einstelligen lineraren Kongruenzgeneratoren verfügen, aber trotzdem genauso schnell sind wie diese. Zeitmessungen einer solchen Beispielimplementation in Java haben ergeben, dass nur ca. 8 CPU-Takte pro K-Bit langem Zufallswert benötigt werden. Bei einem heutzutage üblichen N=64 Bit-Prozessor kann man also maximal K=64/2=32 Bit, also 4 Byte pro Schritt erzeugen, was dann ca. 8/4=2 CPU-Takte pro Zufallsbyte ergeben würde. Bei einer ebenfalls nicht unüblichen CPU-Taktrate von 4GHz sind das ca. 5*10^-10 Sekunden pro erzeugtes Zufallsbyte.

Ebenfalls wichtig ist die Feststellung, dass man im Gegensatz zu allen anderen mir bekannten Multiply-With-Carry-Generatoren, weder höhere Mathematikkenntnisse braucht, um das Funktionsprinzip des Zufallsgenerators zu verstehen, noch irgendwelche langen Primzahlen erzeugen oder kennen muß, um den Zufallsgenerator dann auch verwenden zu können. Es ist auch keine rechenintensive Ordungsbestimmung einer Basis innerhalb einer multiplikativen Gruppe notwendig, nur um die Periode des Zufallsgenerators zu bestimmen. Obendrein läßt sich ein mehrstelliger linearer Kongruenzgenerator im Gegensatz zu den Mersenne-Twister-Generatoren auch noch wesentlich einfacher implementieren.

--Aragorn321 (Diskussion) 12:28, 10. Mai 2016 (CEST)

Kongruenzmethode?

Was versteht man eigentlich unter der Kongruenzmethode? Verwendet der Kongruenzgenerator eine Kongruenzmethode?--Harald321 (Diskussion) 20:16, 26. Aug. 2016 (CEST)