Inverser Kongruenzgenerator - LinkFang.de





Inverser Kongruenzgenerator


Ein inverser Kongruenzgenerator ist ein arithmetischer Zufallszahlengenerator, der durch den Satz von Marsaglia bekannte Nachteile linearer Kongruenzgeneratoren vermeidet. Insbesondere lässt er keine Hyperebenen entstehen. Verwendet man Zufallszahlen inverser Kongruenzgeneratoren für die Box-Muller-Methode, so wird ein Spiralverhalten vermieden. Im Gegenzug verlangt er einen höheren Rechenaufwand.

Allgemeines

Er besteht aus folgenden Komponenten:

  • Modul [math]p \in \mathbb{P}[/math] ([math]\mathbb{P}[/math] steht hierbei wie üblich für die Menge der Primzahlen)
  • Faktor [math]a \in \{0, ... , p-1\}[/math]
  • Inkrement [math]b \in \{0, ... , p-1\}[/math]
  • Startwert [math]y_0 \in \{0, ... , p-1\}[/math]

Der Generator arbeitet nach folgendem Bildungsgesetz:

[math]y_{n+1} = (a y_n^{-1} + b) \, \bmod \, p = ( a y_n^{p-2} + b ) \, \bmod \, p[/math]

Zur Erklärung der Symbolik siehe den Artikel Modulo.

Wegen [math]p\in\mathbb{P}[/math] gibt es zu jedem [math]y_n \ne 0[/math] ein eindeutiges multiplikativ inverses Element [math]y_n^{-1}[/math], so dass [math]y_n \, y_n^{-1} \equiv 1[/math]. Nur für [math]y_n = 0[/math] muss man sich noch Gedanken machen. Rein formal wäre [math]\infty[/math] das inverse Element von [math]0[/math]. Da [math]\infty[/math] nicht darstellbar ist, wird es am besten übersprungen, indem man [math]0^{-1} = 0[/math] setzt, wie es auch der zweiten Darstellung (mit [math]y_n^{p-2}[/math]) entspricht.

Periodenlänge

Die maximale Periodenlänge kann offenbar [math]p[/math] nicht überschreiten. Erreicht wird diese genau dann, wenn das Polynom

[math]x^2 - bx -a[/math]

ein primitives Polynom in [math]\mathbb{Z}_p[/math] ist.

Hyperebenenverhalten

Im Gegensatz zu linearen Kongruenzgeneratoren, deren Werte ja auf wenigen Hyperebenen liegen, kann man hier zeigen, dass gilt:

Jede Hyperebene in [math]\mathbb{Z}_p^k[/math] enthält maximal [math]k[/math] Punkte der Form
[math](x_1,\dots,x_k), (x_2,\dots,x_{k+1}),\dots[/math]
solange [math]x_l\cdots x_{l+k-2} \ne 0[/math] gilt. Durch diese Bedingung scheiden genau [math]k-1[/math] Punkte aus. Dabei ist [math]k\geq 2[/math] beliebig wählbar.

Inverse Generatoren mit zusammengesetztem Modul

Um die Modulodivision durch das Abschneiden der höchstwertigen Bits ersetzen zu können, wäre es angenehm, Moduln [math]m[/math] für die Berechnungsvorschrift

[math]y_{n+1} = ( a y_n^{p-2} + b ) \, \bmod \, m[/math]

zuzulassen, die keine Primzahl, sondern eine Potenz von 2 sind. Dazu muss [math]y_0[/math] ungerade sein, und [math]a,b[/math] müssen so festgelegt werden, dass alle [math]y_n[/math] ungerade sind, denn dann kann das inverse Element zu [math]y_n[/math] eindeutig berechnet werden. Die Periodenlänge beträgt höchstens [math]m/2[/math]. Falls folgende Bedingungen erfüllt sind, beträgt sie genau [math]m/2[/math]:

  • [math]m=2^e \; \; \mbox{mit} \; \; e\geq 3[/math]
  • [math]a \equiv 1 \; (\bmod 4)[/math]
  • [math]b \equiv 2 \; (\bmod 4)[/math]

Explizite inverse Generatoren

Manchmal liest man auch die Definition

[math]y_{n+1} = (a n + b)^{-1} \mod p = ( a n + b )^{p-2}\, \bmod\, p[/math]

oder auch

[math]y_{n+1} = (a (n+y_0) + b)^{-1} \mod p = ( a (n+y_0) + b )^{p-2}\, \bmod\, p[/math]

Letzteres stellt keine Verallgemeinerung dar; man erhält durch Ausmultiplizieren sofort die obige Gestalt.

Periodenlänge

Die maximale Periodenlänge beträgt wieder [math]p[/math], und wird erreicht, falls [math]a\ne 0[/math] gilt.

Literatur

  • Harald Niederreiter: Random Number Generation and Quasi-Monte Carlo Methods. Society for Industrial & Applied Mathematics, Philadelphia PA 1992, ISBN 0-89871-295-5 (Regional Conference Series in Applied Mathematics 63).

Kategorien: Pseudozufallszahlengenerator | Zahlentheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Inverser Kongruenzgenerator (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.