Zufallszahlen
← Eingabe mit scanf | ● | Zufallszahlengenerator →
Der Ablauf eines Programms ist in jedem Fall vorhersagbar, d.h. deterministisch. Dies widerspricht dem Prinzip der Zufallszahlen. Der Computer berechnet daher keine echt zufälligen Zahlen, sondern sogenannte pseudo-zufällige Zahlenreihen der Form
Die Zahlen wiederholen sich spätestens nach der Periode $n$, d.h. $z_{i+n}=z_i$. Man wählt daher die Periode möglichst groß und erhält eine normierte Zufallszahl $x_i \in [0,1]$ mittels Division durch $n-1$:
Der Startwert $z_0$ (Seed) definiert eindeutig die Zahlenfolge. Mit dem gleichen Startwert ergibt sich zwingend die selbe Zahlenfolge.
Ein einfaches Beispiel hierfĂĽr ist der lineare Kongruenz-Generator:
FĂĽr die Bedingung $ggT(q,n)=1$ und $ggT(p,n)|q$, ergeben sich fĂĽr jeden beliebigen Startwert $z_0$ genau $n$ verschiedene hintereinander folgende Zahlen im Bereich [0..n-1]. Die $n+1$te Zahl entspricht wieder dem Startwert.
Zum Beispiel ergibt sich folgende Zahlenreihe fĂĽr $n=11$ mit $p=23$, $q=5$ und dem Startwert $z_0=1$:
$z_0=1$
$z_1=6$
$z_2=0$
$z_3=5$
$z_4=10$
$z_5=4$
$z_6=9$
$z_7=3$
$z_8=8$
$z_9=2$
$z_{10}=7$
$z_{11}=1$
Eine wenig zufällige Folge kann sich jedoch ergeben, selbst wenn die obige Bedingung erfüllt ist. Ein Beispiel dafür ist die Kombination $p=12$ und $q=1$:
$z_0=1$
$z_1=2$
$z_2=3$
$z_3=4$
$z_4=5$
$z_5=6$
$z_6=7$
$z_7=8$
$z_8=9$
$z_9=10$
$z_{10}=0$
$z_{11}=1$
Zur Vermeidung solch schlechter Zufallszahlenreihen, muss zusätzlich noch die Bedingung $n|p-1$ gelten ($n\nep-1$).
Die Verteilung der Zufallszahlen erscheint zufällig, ist aber nicht echt zufällig. Die Folge erfüllt zwar die stochastische Eigenschaft der Gleichverteilung aller Zufallszahlen, die Zufallszahlen sind aber nicht stochastisch unabhängig, weil polynomal vorhersagbar. In der Praxis ist dies aber von untergeordneter Bedeutung. Für strenge stochastische Anforderungen existieren auch Zufallszahlenreihen, die nicht polynomal vorhersagbar sind.
← Eingabe mit scanf | ● | Zufallszahlengenerator →