www.wikidata.de-de.nina.az

Inverser Kongruenzgenerator Ein inverser Kongruenzgenerator ist ein arithmetischer Zufallszahlengenerator der durch den

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 Bearbeiten

Er besteht aus folgenden Komponenten:

  • Modul ( steht hierbei wie üblich für die Menge der Primzahlen)
  • Faktor
  • Inkrement
  • Startwert

Der Generator arbeitet nach folgendem Bildungsgesetz:

Zur Erklärung der Symbolik siehe den Artikel Modulo.

Wegen gibt es zu jedem ein eindeutiges multiplikativ inverses Element , so dass . Nur für muss man sich noch Gedanken machen. Rein formal wäre das inverse Element von . Da nicht darstellbar ist, wird es am besten übersprungen, indem man setzt, wie es auch der zweiten Darstellung (mit ) entspricht.

Periodenlänge Bearbeiten

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

ein primitives Polynom in ist.

Hyperebenenverhalten Bearbeiten

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

solange gilt. Durch diese Bedingung scheiden genau Punkte aus. Dabei ist beliebig wählbar.

Inverse Generatoren mit zusammengesetztem Modul Bearbeiten

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

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

Programmierung Bearbeiten

Das folgende Programm in der Programmiersprache C++ zeigt die Implementierung eines inversen Kongruenzgenerators mit , und . Es erzeugt 10 Zufallszahlen, die in einem Array gespeichert werden. Das multiplikativ inverse Element von modulo wird mit dem erweiterten euklidischen Algorithmus bestimmt. Bei der Ausführung des Programms wird die Hauptfunktion main verwendet, die die Zufallszahlen auf der Konsole ausgibt.

#include <iostream> using namespace std; // Diese Funktion bestimmt das multiplikative Inverse von a modulo b mithilfe des erweiterten euklidischen Algorithmus int getModularMultiplicativeInverse(int a, int b) {  if (a == 0)  {  return 0; // Spezialfall: Inverses von 0  }  int d = 1; // Deklaration der lokalen Variablen  int t = 0;  int u = 0;  int v = 1;  while (b != 0)  {  int q = a / b;  int b1 = b; // Variable zum Zwischenspeichern  b = a - q * b;  a = b1;  int u1 = u; // Variable zum Zwischenspeichern  u = d - q * u;  d = u1;  }  return d; } // Funktion, die die Zufallszahlen erzeugt int* inversiveCongruentialGenerator(int y0, int p, int a, int b, int count) {  int* randomNumbers = new int[count]; // Initialisiert das Array für die Zufallszahlen  randomNumbers[0] = y0; // Startwert für den Zufallszahlengenerator  for (int i = 0; i < count; i++)  {  randomNumbers[i] = (a * getModularMultiplicativeInverse(randomNumbers[i - 1], p) + b) % p;  }  return randomNumbers; } // Hauptfunktion die das Programm ausführt int main() {  int y0 = 0; // Deklaration der lokalen Variablen  int p = 21269;  int a = 8;  int b = 3;  int count = 10;  int* randomNumbers = inversiveCongruentialGenerator(y0, p, a, b, count); // Aufruf der Funktion  for (int i = 0; i < count; i++)  {  cout << randomNumbers[i] << endl; // Ausgabe auf der Konsole  } }

Explizite inverse Generatoren Bearbeiten

Manchmal liest man auch die Definition

oder auch

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

Periodenlänge Bearbeiten

Die maximale Periodenlänge beträgt wieder und wird erreicht, falls gilt.

Siehe auch Bearbeiten

Literatur Bearbeiten

  • 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).
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Ein inverser Kongruenzgenerator ist ein arithmetischer Zufallszahlengenerator der durch den Satz von Marsaglia bekannte Nachteile linearer Kongruenzgeneratoren vermeidet Insbesondere lasst er keine Hyperebenen entstehen Verwendet man Zufallszahlen inverser Kongruenzgeneratoren fur die Box Muller Methode so wird ein Spiralverhalten vermieden Im Gegenzug verlangt er einen hoheren Rechenaufwand Inhaltsverzeichnis 1 Allgemeines 1 1 Periodenlange 1 2 Hyperebenenverhalten 1 3 Inverse Generatoren mit zusammengesetztem Modul 1 4 Programmierung 2 Explizite inverse Generatoren 2 1 Periodenlange 3 Siehe auch 4 LiteraturAllgemeines BearbeitenEr besteht aus folgenden Komponenten Modul p P displaystyle p in mathbb P nbsp P displaystyle mathbb P nbsp steht hierbei wie ublich fur die Menge der Primzahlen Faktor a 0 p 1 displaystyle a in 0 p 1 nbsp Inkrement b 0 p 1 displaystyle b in 0 p 1 nbsp Startwert y 0 0 p 1 displaystyle y 0 in 0 p 1 nbsp Der Generator arbeitet nach folgendem Bildungsgesetz y n 1 a y n 1 b mod p a y n p 2 b mod p displaystyle y n 1 ay n 1 b bmod p ay n p 2 b bmod p nbsp Zur Erklarung der Symbolik siehe den Artikel Modulo Wegen p P displaystyle p in mathbb P nbsp gibt es zu jedem y n 0 displaystyle y n neq 0 nbsp ein eindeutiges multiplikativ inverses Element y n 1 displaystyle y n 1 nbsp so dass y n y n 1 1 displaystyle y n y n 1 equiv 1 nbsp Nur fur y n 0 displaystyle y n 0 nbsp muss man sich noch Gedanken machen Rein formal ware displaystyle infty nbsp das inverse Element von 0 displaystyle 0 nbsp Da displaystyle infty nbsp nicht darstellbar ist wird es am besten ubersprungen indem man 0 1 0 displaystyle 0 1 0 nbsp setzt wie es auch der zweiten Darstellung mit y n p 2 displaystyle y n p 2 nbsp entspricht Periodenlange Bearbeiten Die maximale Periodenlange kann offenbar p displaystyle p nbsp nicht uberschreiten Erreicht wird diese genau dann wenn das Polynom x 2 b x a displaystyle x 2 bx a nbsp ein primitives Polynom in Z p displaystyle mathbb Z p nbsp ist Hyperebenenverhalten Bearbeiten Im Gegensatz zu linearen Kongruenzgeneratoren deren Werte ja auf wenigen Hyperebenen liegen kann man hier zeigen dass gilt Jede Hyperebene in Z p k displaystyle mathbb Z p k nbsp enthalt maximal k displaystyle k nbsp Punkte der Form x 1 x k x 2 x k 1 displaystyle x 1 dots x k x 2 dots x k 1 dots nbsp dd solange x l x l k 2 0 displaystyle x l cdots x l k 2 neq 0 nbsp gilt Durch diese Bedingung scheiden genau k 1 displaystyle k 1 nbsp Punkte aus Dabei ist k 2 displaystyle k geq 2 nbsp beliebig wahlbar Inverse Generatoren mit zusammengesetztem Modul Bearbeiten Um die Modulodivision durch das Abschneiden der hochstwertigen Bits ersetzen zu konnen ware es angenehm Moduln m displaystyle m nbsp fur die Berechnungsvorschrift y n 1 a y n p 2 b mod m displaystyle y n 1 ay n p 2 b bmod m nbsp zuzulassen die keine Primzahl sondern eine Potenz von 2 sind Dazu muss y 0 displaystyle y 0 nbsp ungerade sein und a b displaystyle a b nbsp mussen so festgelegt werden dass alle y n displaystyle y n nbsp ungerade sind denn dann kann das inverse Element zu y n displaystyle y n nbsp eindeutig berechnet werden Die Periodenlange betragt hochstens m 2 displaystyle m 2 nbsp Falls folgende Bedingungen erfullt sind betragt sie genau m 2 displaystyle m 2 nbsp m 2 e mit e 3 displaystyle m 2 e mbox mit e geq 3 nbsp a 1 mod 4 displaystyle a equiv 1 bmod 4 nbsp b 2 mod 4 displaystyle b equiv 2 bmod 4 nbsp Programmierung BearbeitenDas folgende Programm in der Programmiersprache C zeigt die Implementierung eines inversen Kongruenzgenerators mit p 21269 displaystyle p 21269 nbsp a 8 displaystyle a 8 nbsp und b 3 displaystyle b 3 nbsp Es erzeugt 10 Zufallszahlen die in einem Array gespeichert werden Das multiplikativ inverse Element von y n displaystyle y n nbsp modulo p displaystyle p nbsp wird mit dem erweiterten euklidischen Algorithmus bestimmt Bei der Ausfuhrung des Programms wird die Hauptfunktion main verwendet die die Zufallszahlen auf der Konsole ausgibt include lt iostream gt using namespace std Diese Funktion bestimmt das multiplikative Inverse von a modulo b mithilfe des erweiterten euklidischen Algorithmus int getModularMultiplicativeInverse int a int b if a 0 return 0 Spezialfall Inverses von 0 int d 1 Deklaration der lokalen Variablen int t 0 int u 0 int v 1 while b 0 int q a b int b1 b Variable zum Zwischenspeichern b a q b a b1 int u1 u Variable zum Zwischenspeichern u d q u d u1 return d Funktion die die Zufallszahlen erzeugt int inversiveCongruentialGenerator int y0 int p int a int b int count int randomNumbers new int count Initialisiert das Array fur die Zufallszahlen randomNumbers 0 y0 Startwert fur den Zufallszahlengenerator for int i 0 i lt count i randomNumbers i a getModularMultiplicativeInverse randomNumbers i 1 p b p return randomNumbers Hauptfunktion die das Programm ausfuhrt int main int y0 0 Deklaration der lokalen Variablen int p 21269 int a 8 int b 3 int count 10 int randomNumbers inversiveCongruentialGenerator y0 p a b count Aufruf der Funktion for int i 0 i lt count i cout lt lt randomNumbers i lt lt endl Ausgabe auf der Konsole Explizite inverse Generatoren BearbeitenManchmal liest man auch die Definition y n 1 a n b 1 mod p a n b p 2 mod p displaystyle y n 1 an b 1 mod p an b p 2 bmod p nbsp oder auch y n 1 a n y 0 b 1 mod p a n y 0 b p 2 mod p displaystyle y n 1 a n y 0 b 1 mod p a n y 0 b p 2 bmod p nbsp Letzteres stellt keine Verallgemeinerung dar man erhalt durch Ausmultiplizieren sofort die obige Gestalt Periodenlange Bearbeiten Die maximale Periodenlange betragt wieder p displaystyle p nbsp und wird erreicht falls a 0 displaystyle a neq 0 nbsp gilt Siehe auch BearbeitenKongruenzgenerator Erweiterter euklidischer AlgorithmusLiteratur BearbeitenHarald Niederreiter Random Number Generation and Quasi Monte Carlo Methods Society for Industrial amp Applied Mathematics Philadelphia PA 1992 ISBN 0 89871 295 5 Regional Conference Series in Applied Mathematics 63 Abgerufen von https de wikipedia org w index php title Inverser Kongruenzgenerator amp oldid 227666800