Zufallszahlengeneratoren
In Computerprogrammen werden "Zufallszahlen" nach bestimmten Algorithmen
berechnet, d.h. es sind gar keine echten Zufallszahlen, sondern "Pseudozufallszahlen".
Von den so bestimmten Pseudozufallszahlen verlangt man eine möglichst
gute Annäherung an "echte" Zufallszahlen, z.B. sollten die einzelnen
Ziffern mit gleicher relativer Häufigkeit auftreten, Wiederholungen
von Ziffern sollten die gleiche relative Häufigkeit wie bei echten
Zufallsziffern haben, usw.
Eingabe
Hier können extern erzeugte Zufallszahlen eingefügt oder von internen Zufallszahlengeneratoren erzeugt werden. Die Auswertung
entnimmt man den folgenden Analysen.
Häufigkeitsanalyse
Die relative Häufigkeit der Ziffern 0 bis 9 wird angezeigt.
Pokertest
Beim Pokertest werden die Zufallszahlen in Fünfergruppen zerlegt und
die relative Häufigkeit der vom Pokerspiel her bekannten Muster wird
gezählt und mit dem Erwartungswert verglichen.
Maximumtest
Beim Maximumtest wird wie beim Pokertest die Verteilung der Ziffern geprüft.
Die Zufallszahlen werden in Dreiergruppen abc zerlegt und es wird gezählt,
mit welcher relativen Häufigkeit die Ziffer b die größte
Ziffer der Gruppe ist. Bei Gleichverteilung sollte die relative Häufigkeit
0,285 sein.
Anhang
Generator vom Rechenfehler-Typ
Er erzeugt Pseudozufallszahlen im Intervall (0;1). Zu einer (vorgegebenen)
Anfangsvariable x wird z.B. 3,1415... addiert, die Zahl wird mit 8 potenziert
und vom Ergebnis der Nachkommateil als neue Pseudozufallszahl ausgegeben.
Hier werden also Fehler, die wegen der begrenzten Rechengenauigkeit auftreten,
als Pseudozufallsziffern benützt. Hier der Quellcode:
function rnd() /* Zufallszahl R in (0,1) */
{ R=Math.pow(R+A,8);
R-=Math.floor(R);
return R;
}
Im vorliegenden Fall gilt als Initialisierung:
var R=0.01*dat.getMinutes()+0.1*dat.getSeconds();
Anmerkung: Bei diesem Generator treten nach etlichen Wiederholungen sogar
Unterschiede zwischen einzelnen JavaScript-Interpretern (Netscape - Explorer)
auf, die den Algorithmus für krytographische Zwecke unbrauchbar machen kann:
Verschlüsselung im Explorer kann nur wieder im Explorer entschlüsselt werden.
Rechenfehler-Typ 2
Eine andere Möglichkeit besteht z.B. in der Berechnung von irrationalen
Logarithmen logba mit 1< a < b. Wegen der Rechenfehler
werden die Nachkommastellen schnell pseudozufällig. Hier ein möglicher
Quellcode (a=2, b=10):
var a=2,b=10;
function rnd()
{ var r=0,i=2;
while(i<1000000) /* 1/i ist die letzte mögliche Dezimalstelle */
{ a*=a;
if(a>=b){a/=b;
r=1/i+r;
}
i*=2;
}
return r;
}
| Hier können Sie andere Werte für a und b eingeben
(Achtung: 1
< a < b !)
|
Linearer Kongruenz Algorithmus
Eine Startzahl S ("Seed") wird mit der Zahl A multipliziert, die Zahl B wird addiert.
Das Ergebnis wird modulo M genommen, das ergibt die neue Zahl S. S/M ist
eine Pseudozufallszahl in [0,1).Hier der Quellcode des Generators.
function rnd()
{ S=(A*S+B)%M;
return S/M;
}
Im vorliegenden Fall gilt als Initialisierung:
var A=11113,B=1,M=524288,S=1123;
Günstige bzw. ungünstige Wahlen:
Nach Knuth erhält man für M=2n die maximale Periodenlänge, wenn B
ungerade und A mod 4 = 1 gilt. Da die Modulo-Arithmetik bei Integer-Typen
"automatisch" durch Überlauf eingebaut ist, wird man meist M als
Zweierpotenz wählen.
(In JavaScript hat man dabei jedoch Probleme: Es wird auf
Gleitkomma-Arithmetik umgeschaltet. Im vorliegenden Fall n=19, A=11113, B=1 tritt noch keine
Umschaltung ein)
Allgemeiner erhält man maximale
Periodenlänge, wenn ggT(B;M)=1 und A-1 ein Vielfaches jedes Primfaktors von M
und - falls M ein Vielfaches von 4 auch A-1 ein Vielfaches von 4 ist.
Literatur
A. Engel: Mathematisches Experimentieren mit dem PC, Klett 1991, ISBN 3-12-983360-9
A.Engel: Stochastik, Klett 1987, ISBN 3-12-983110-X
D.E. Knuth: The Art of Computer Programming, Vol.2, Addison-Wesley 1998, ISBN 0-201-89684-2
Fehler, Anregungen bitte an Thomas Gebhardt