 |
Linear kongruente Zufallsgeneratoren
Diese Generatoren verwenden eine Rekursionsrelation
für ganze Zahlen Ij
In+1 = a In + c
(mod m)
mit geeignet gewählten ganzzahligen a, c, m.
Erfahrung zeigt, daß die Wahl c=0 bei guter Wahl
von a und m keine Einschränkung darstellt.
- Die Periode eines solchen Generators ist höchstens m.
m sollte also möglichst groß gewählt werden.
Bei kleinen Werten von m kann man je nach Wahl der anderen Parameter
in einem Plot der Paare
(In-1,In)
deutlich sehen, daß diese Paare auf wenigen Geraden liegen,
also eine starke Paar-Korrelation besteht.
- Binder und Stauffer diskutieren in Kapitel 1.1.1 des Buches
[1] als Hauptbeispiel
a = 65539,
m = 231 = 2147483648,
c = 0.
(dieses a ist eine Primzahl).
Binder und Stauffer bemerken selbst, daß dies kein besonders
guter Generator ist. Der Kommentar in Kapitel 7.1 von [2]
zu diesem auch sonst verbreiteten Generator ist hingegen vernichtend:
``... choices of m, a, and c have been botched''
(``verpfuscht''). Ein Problem liegt in den Triplet-Korrelationen -
neben der Tatsache, daß der Generator nicht mit geraden Zahlen
gestartet werden darf und dann auch nur ungerade Zahlen liefert.
- Die Empfehlung von [2]
für einen ``Minimalen Standard'' Generator lautet:
a = 75 = 16807,
m = 231 - 1 = 2147483647,
c = 0.
Dies ist ein guter Generatoren innerhalb dieser Klasse.
Auch ein guter linear kongruenter Generator hat Probleme:
- Die niedrigen Bits der Ij sind weniger
zufällig als die hohen. Wird nur ein kleinerer Wertebereich
benötigt, sollte man also nie die
unteren, sondern immer nur die oberen Bits verwenden.
- Die Periode ist vergleichsweise kurz, d.h. man erhält
typerischerweise maximal etwa 109 verschiedene
Ij, danach wiederholt sich die Zahlenfolge.
Literatur:
-
K. Binder, D. Stauffer, A Simple Introduction to Monte Carlo Simulation
and Some Specialized Topics, in: Applications of the Monte Carlo
Method, K. Binder (Hrsg.), Springer Berlin (1984)
-
W.H. Press, S.A. Teukolsky, W.T. Vetterling, B.P. Flannery,
Numerical Recipes in C,
Cambridge University Press (1992)
|
|
