Inverser Kongruenzgenerator

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.

Inhaltsverzeichnis

Allgemeines

Er besteht aus folgenden Komponenten:

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

Der Generator arbeitet nach folgendem Bildungsgesetz:

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

Zur Erklärung der Symbolik siehe den Artikel Modulo.

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

Periodenlänge

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

x2bxa

ein primitives Polynom in \mathbb{Z}_p ist.

Hyperebenenverhalten

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

Jede Hyperebene in \mathbb{Z}_p^k enthält maximal k Punkte der Form
(x_1,\dots,x_k), (x_2,\dots,x_{k+1}),\dots
solange x_l\cdots x_{l+k-2} \ne 0 gilt. Durch diese Bedingung scheiden genau k − 1 Punkte aus. Dabei ist k\geq 2 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 m für die Berechnungsvorschrift

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

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

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

Explizite inverse Generatoren

Manchmal liest man auch die Definition

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

oder auch

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

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

Periodenlänge

Die maximale Periodenlänge beträgt wieder p, und wird erreicht, falls a\ne 0 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).

Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Kongruenzgenerator — Die Kongruenzgeneratoren bilden eine Klasse von Algorithmen, die zufällig aussehende Zahlenfolgen erzeugen. Die dadurch erzeugten Zahlen nennt man Pseudozufallszahlen, da sie deterministisch erzeugt werden und somit nicht wirklich zufällig sind.… …   Deutsch Wikipedia

  • Allgemeiner Kongruenzgenerator — Die Kongruenzgeneratoren bilden eine Klasse von Algorithmen, die zufällig aussehende Zahlenfolgen erzeugen. Die dadurch erzeugten Zahlen nennt man Pseudozufallszahlen, da sie deterministisch erzeugt werden und somit nicht wirklich zufällig sind.… …   Deutsch Wikipedia

  • Fibonacci-Kongruenzgenerator — Die Kongruenzgeneratoren bilden eine Klasse von Algorithmen, die zufällig aussehende Zahlenfolgen erzeugen. Die dadurch erzeugten Zahlen nennt man Pseudozufallszahlen, da sie deterministisch erzeugt werden und somit nicht wirklich zufällig sind.… …   Deutsch Wikipedia

  • Gemischter linearer Kongruenzgenerator — Die Kongruenzgeneratoren bilden eine Klasse von Algorithmen, die zufällig aussehende Zahlenfolgen erzeugen. Die dadurch erzeugten Zahlen nennt man Pseudozufallszahlen, da sie deterministisch erzeugt werden und somit nicht wirklich zufällig sind.… …   Deutsch Wikipedia

  • Linearer Kongruenzgenerator — Die Kongruenzgeneratoren bilden eine Klasse von Algorithmen, die zufällig aussehende Zahlenfolgen erzeugen. Die dadurch erzeugten Zahlen nennt man Pseudozufallszahlen, da sie deterministisch erzeugt werden und somit nicht wirklich zufällig sind.… …   Deutsch Wikipedia

  • Multiplikativer Kongruenzgenerator — Die Kongruenzgeneratoren bilden eine Klasse von Algorithmen, die zufällig aussehende Zahlenfolgen erzeugen. Die dadurch erzeugten Zahlen nennt man Pseudozufallszahlen, da sie deterministisch erzeugt werden und somit nicht wirklich zufällig sind.… …   Deutsch Wikipedia

  • Fibonacci-Generator — Die Kongruenzgeneratoren bilden eine Klasse von Algorithmen, die zufällig aussehende Zahlenfolgen erzeugen. Die dadurch erzeugten Zahlen nennt man Pseudozufallszahlen, da sie deterministisch erzeugt werden und somit nicht wirklich zufällig sind.… …   Deutsch Wikipedia

  • Fibonaccigenerator — Die Kongruenzgeneratoren bilden eine Klasse von Algorithmen, die zufällig aussehende Zahlenfolgen erzeugen. Die dadurch erzeugten Zahlen nennt man Pseudozufallszahlen, da sie deterministisch erzeugt werden und somit nicht wirklich zufällig sind.… …   Deutsch Wikipedia

  • Fibonaccikongruenzgenerator — Die Kongruenzgeneratoren bilden eine Klasse von Algorithmen, die zufällig aussehende Zahlenfolgen erzeugen. Die dadurch erzeugten Zahlen nennt man Pseudozufallszahlen, da sie deterministisch erzeugt werden und somit nicht wirklich zufällig sind.… …   Deutsch Wikipedia

  • Satz von Knuth — Die Kongruenzgeneratoren bilden eine Klasse von Algorithmen, die zufällig aussehende Zahlenfolgen erzeugen. Die dadurch erzeugten Zahlen nennt man Pseudozufallszahlen, da sie deterministisch erzeugt werden und somit nicht wirklich zufällig sind.… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”