Kongruenzgenerator - Startwert bestimmen

12.10.2010, 21:26	Silv3rSurf3r	Auf diesen Beitrag antworten »
Kongruenzgenerator - Startwert bestimmen Hallo Leute, ich versuche gerade eine Aufgabe zu Linearen Kongruenzgeneratoren (LCG) nachzuvollziehen: LCG haben die Form $\begin{eqnarray} x_{i+1}=ax_{i}+b~ mod ~m \end{eqnarray}$ zur Erzeugung von gleichverteiliten, ganzzahligen Pseudozufallszahlen. In einer Übung haben wir gezeigt, dass es Startwerte $\begin{eqnarray} x_{0} \end{eqnarray}$ gibt, zu denen Orbits der Periodenlänge 1 gehören. Konkret haben wir das mit $\begin{eqnarray} a=7,b=6~ und~ m=64 \end{eqnarray}$ durchgeführt. Gezeigt haben wir das dann so: $\begin{eqnarray} x_{i+1}=7x_{i}+6~ mod ~64 => x_{i+1}=7x_{i}+6+k64, k \in \mathbb Z \end{eqnarray}$ Für Orbit 1: $\begin{eqnarray} x_{1}=x_{0} \end{eqnarray}$ einsetzen: $\begin{eqnarray} => x_{0}=7x_{0}+6+k64 => x_{0}=-1-\frac{64}{6}k \end{eqnarray}$ Bis hier ist ja alles klar. Jetzt haben wir aber folgendes aufgeschrieben: $\begin{eqnarray} -k=n3 \in \mathbb Z => x_{0} \in \{31,63\} \text{für}~~ k=-3,k=-6 \end{eqnarray*}$ Diesen letzten Schritt kann ich nicht nachvollziehen, kann mir da jemand von euch helfen? LG
18.10.2010, 03:20	Iridium	Auf diesen Beitrag antworten »
Hi, Ich denke mal, daß man $\begin{eqnarray} -k = 3n \end{eqnarray}$ setzt, damit sich die 6 im Nenner zu etwas wegkürzen kann, so daß der Bruch zu einer ganzen Zahl führt, denn die Elemente die durch den LCG aufeinander abgebildet sind, sind ja erst mal ganze Zahlen. Wenn du also -k als Vielfaches von 3 setzt, dann steht da nur noch 64/2, was zu 32 wird, woraus du dann die erste Lösung -1+32=31 erhälst. Die zweite Lösung ergibt sich entsprechend, wenn man die 6 gleich ganz wegkürzt. Gruß edit: In welchem Zusammenhang macht ihr das? Informatik mit Pseudozufallszahlenerzeugung als Schwerpunkt? editedit: Man kann die Lösungen glaube ich auch graphisch bestimmen (als Schnittpunkte von y = a x + b (mod m) mit y = x?)

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »