WikiDer > Kongruenzgenerator

EIN Kongruenzgenerator ist ein Algorithmus, der Pseudozufallszahlen erzeugt also Zahlenfolgen, die deterministisch erzeugt werden und somit nicht wirklich zufällig sind, aber viele Eigenschaften von zufällige Zahlen haben. Kongruenzgeneratoren sind die bekanntesten und am häufigsten verwendeten Pseudozufallszahlengeneratoren.

Ein Kongruenzgenerator wird durch folgende Parameter bestimmt:

• die Anzahl der Zustandswerte ${displaystyle n}$
• der Modul ${displaystyle minus {2,3,4,ldots}}$
• die Multiplikatoren ${displaystyle a_{1},ldots ,a_{n}in links{0,ldots ,m-1ight}}$
• der Anstieg ${displaystyle bin left{0,ldots ,m-1ight}}$

und der Algorithmus, mit dem eine neu generierte Zahl für ${displaystyle i>n}$ bis zum wiederkehrende Beziehung:

${displaystyle y_{i}=Summe _{k=1}^{n}a_{k}y_{i-k} b{pmod {m}}}$.

Darin sind ${displaystyle y_{1},ldots ,y_{n}in links{0,ldots ,m-1ight}}$ die Startwerte.

Reelle Zufallszahlen im Intervall [0, 1] erhält man als ${displaystyle u_{i}=y_{i}/m}$, unter der Vorraussetzung, dass ${displaystyle m}$ groß genug, um eine ausreichend genaue Unterteilung zu geben.

Der Zustand des Generators für die Produktion von ${displaystyle y_{i}}$ ist durch die Startwerte gegeben. Dieser Zustand setzt (für gegeben ${displaystyle n}$, ${displaystyle m}$, ${displaystyle k}$, ${displaystyle b}$) alle nachfolgenden Zufallszahlen, da die nächste Zufallszahl und der nächste Zustand durch den aktuellen Zustand bestimmt werden. Es gibt ${displaystyle m^{n}}$ möglichen Zuständen, also nach Maximum ${displaystyle m^{n}}$ Schritte werden in einem vorherigen Zustand wiederholt. Der Kongruenzgenerator erzeugt also eine periodische Zahlenfolge, deren Periodenlänge viel kleiner als ist ${displaystyle m^{n}}$ könnte sein. Im Extremfall ist die Länge 1 und der Generator gibt immer die gleiche "Zufallszahl" aus. Bei der Wahl der Parameter ist daher unter anderem auf einen ausreichend langen Zeitraum zu achten.

Lineare Kongruenz

wenn ${Anzeigestil n=1}$, man spricht von a linearer Kongruenzgenerator. Der Algorithmus ist:

${displaystyle y_{i}=a,y_{i-1} b{pmod {m}}}$.

Ist auch noch ${displaystyle b=0}$, So

${displaystyle y_{i}=a,y_{i-1}{pmod {m}}}$,

dann gibt es a multiplikativer Kongruenzgenerator. Die multiplikative Kongruenz wird auch Lehmer-Kongruenz genannt, nach D. H. Lehmer der diesen Algorithmus 1949 eingeführt hat.

Fibonacci-Generator

Ein Fibonacci-Generator ist ein Kongruenzgenerator mit ${Anzeigestil n=2}$, ${displaystyle b=0}$ und ${displaystyle a_{1}=a_{2}=1}$, und besteht aus folgenden Komponenten:

• Modul ${displaystyle minus {2,3,4,ldots}}$
• Startwerte ${displaystyle y_{1},y_{2}in links{0,ldots ,m-1ight}}$

Die folgende Funktion generiert die Pseudozufallszahlen:

${displaystyle y_{i}equiv y_{i-1} y_{i-2}{pmod {m}}quad({mbox{with }}igeq 3)}$.

Ein Merkmal ist, dass die Fälle ${displaystyle y_{i-1}$ beziehungsweise ${displaystyle y_{i}$ nie vorkommen. Fibonacci-Generatoren eignen sich daher nicht als Pseudo-Zufallsgeneratoren. Dies gilt insbesondere für mathematische Objekte, die die Erzeugung von mehr als zwei Zufallszahlen erfordern. Versucht man beispielsweise eine beliebige Punktwolke in einem Würfel zu erzeugen, würden alle Punkte auf zwei Flächen liegen.

Verzögerter Fibonacci-Generator

Das Prinzip des Fibonacci-Generators lässt sich nicht auf die letzten beiden, sondern auf Werte weiter hinten verallgemeinern ${displaystyle y_{i}}$ um eine neue Zufallszahl zu generieren. Dies führt zu einem verzögerten ('verzögerten') Fibonacci-Generator:

${displaystyle y_{i}equiv y_{i-B} y_{i-A}{pmod {m}}quad {mbox{with}};A,Bin mathbb {N} ^{ }, A>B;Quad i>A}$

mit den Startwerten ${displaystyle y_{1},ldots ,y_{A}in links{0,ldots ,m-1ight}}$.

Dann ist ${Anzeigestil n=A}$ und ${displaystyle a_{A}=a_{B}=1}$ und der andere ${displaystyle a_{k}}$ sind null. Hiermit, ${displaystyle m}$ in der Regel gleich gewählt und ${Anzeigestil A}$ und ${Anzeigestil B}$ so gewählt werden, dass das Polynom in ${Anzeigestil x}$: ${Anzeigestil x^{A} x^{B} 1}$ ein Primitiv Polynom Modul 2. Die Periode des Generators ist dann minimal ${Displaystil 2^{A}-1}$.

${Anzeigestil x^{A} x^{B} 1}$ ist ein primitives Polynom modulo 2 genau dann, wenn ${Anzeigestil x^{A} x^{A-B} 1}$ das ist. Also statt ${Anzeigestil B}$ auch immer ${Anzeigestil A-B}$ Berechnung.

Die folgende Tabelle gibt einige Werte für ${Anzeigestil A}$ und ${Anzeigestil B}$ die diese Bedingung erfüllen:

ein	2	31	55	73	98	100	135	258	607	3217	23209
B	1	13	24	25	27	37	22	83	273	576	9739

Dieser Generator wird auch in der Praxis verwendet. Es gibt jedoch nicht immer völlig zufällige Zahlen. Das Problem des gewöhnlichen Fibonacci-Generators hat sich lediglich verschoben; Komm jetzt ${displaystyle y_{i-A}$ oder ${displaystyle y_{i-B}$ niemals zuvor. Es gibt noch mehr Mängel.

Als Lösung wurde vorgeschlagen, immer nur zu verwenden ${Anzeigestil A}$ fortlaufende Nummern, dann die nächste ${Anzeigestil 4A}$ bis um ${Anzeigestil 10A}$ Zahlen ablehnen. Dies funktioniert gut, führt aber zu einer 5- bis 11-fach höheren Rechenzeit. Der von Donald Knuth vorgeschlagene Raarray-Generator funktioniert auf diese Weise. Hier ist ${Anzeigestil A=100}$ und ${Anzeigestil B=37}$, und von 1009 fortlaufenden Nummern wird nur ein Block mit 100 Nummern verwendet.

Für einen Zeitraum von ${Displaystil 2^{A}-1}$ ist nur das niederwertigste Bit im Zustandswert ${displaystyle y_{i}}$ wichtig, das heißt, es ist wichtig, ob das Bit gerade oder ungerade ist. Es ist möglich, die Bits höherer Ordnung nach Bedarf zu ändern, um die Qualität der resultierenden Zufallszahlen zu verbessern. Beispielsweise:

${displaystyle y_{i}equiv y_{iA} y_{iB} f(y_{iC}){pmod {m}};quad f:{0,ldots ,m-1}ightarrow {0,2,4,6 ,ldots},;Cin {1,ldots,n}}$

Weitere Verallgemeinerung

Man kann den verzögerten Fibonacci-Generator weiter verallgemeinern, indem man mehr als zwei Zustandswerte verarbeitet:

${displaystyle y_{i}Äquiv. Summe _{kin M}y_{i-k}{pmod {m}}quad {mbox{with}}quad Msubset mathbb {N} ^{ }}$.

Hier ist ${displaystyle n}$ das größte Element in ${Anzeigestil M}$. Für einen Zeitraum von mindestens ${Displaystil 2^{n}-1}$ um zu garantieren, auch hier das entsprechende Polynom ${Anzeigestilsumme _{kin M}x^{k} 1}$ oder äquivalent das Polynom ${displaystyle x^{n} Summe _{kin M}x^{n-k}}$ sei ein primitives Polynom modulo 2 (mit geradem Modul ${displaystyle m}$). Ein so gebauter Generator mit ${Anzeigestil |M|>2}$ erzeugt im Allgemeinen bessere Zufallszahlen als mit ${Anzeigestil |M|=2}$, aber das geht auch zu Lasten der Rechenzeit.

Mit weiterer Verallgemeinerung für ein gegebenes ${displaystyle n}$ erhöhen die Länge der Periode und verbessern wahrscheinlich auch die Qualität der Zufallszahlen. ${displaystyle p}$ ist ein Primfaktor von ${displaystyle m}$. Für die Rechenregel

${displaystyle y_{i}Äquiv. Summe _{k=1}^{n}a_{k}y_{i-k}{pmod {m}}}$

wird die ${displaystyle a_{k}in {0,ldots ,m-1}}$, mit ${displaystyle a_{n}nicht gleich 0{pmod {p}}}$, kann so gewählt werden, dass das Polynom in ${Anzeigestil x}$

${displaystyle x^{n}-sum _{k=1}^{n}a_{k}x^{n-k}{pmod {p}}}$

ein primitives Polynom modulo ${displaystyle p}$ ist. Dann ist die Periode mindestens ${displaystyle p^{n}-1}$.

Der vorherige Generator folgt daraus mit ${Anzeigestil p=2}$ und ${displaystyle a_{k}in {0.1}}$ als Sonderfall und ${Anzeigestil n=1; p=m}$ liefert einen multiplikativen Kongruenzgenerator mit Periode ${Anzeigestil p-1}$.

Das Polynom ${displaystyle f(x)=x^{n}-summe _{k=1}^{n}a_{k}x^{n-k}}$ ist ein primitives Polynom modulo p, wenn

${displaystyle r={frac {p^{n}-1}{p-1}}}$ und ${Anzeigestil a=(-1)^{n-1}a_{n}}$

Treffen:

• ${Anzeigestil a}$ ist ein primitives Element modulo ${displaystyle p}$
• das Polynom ${displaystyle x^{r}}$ ist kongruent zu ${Anzeigestil a}$ (modulo ${Anzeigestil f(x)}$)
• für alle Primfaktoren ${Anzeigestil q}$ von ${displaystyle r}$ ist der Grad des Polynoms ${displaystyle x^{r/q}{pmod { }}f(x)}$ positiv.

Dazu wird Polynomrechnung verwendet und modulo ${displaystyle p}$ mit den Koeffizienten berechnet (sie sind Elemente der Quotientenring${displaystyle mathbb {Z} /pmathbb {Z} }$).