\documentclass[12pt]{article}
\usepackage[latin1]{inputenc}
\usepackage{german}

%\textheight=29.7cm \textwidth=21.0cm % DIN A4\n", 
\textheight=24.7cm \textwidth=16cm
\hoffset=-1in \voffset=-1in     % compensate default margins
\topmargin=1.5cm \headheight=0cm \headsep=0cm % text distance from top 
\footskip=1cm % distance footer from bottom of page
\oddsidemargin=2.5cm \evensidemargin=2.5cm

\pagestyle{empty}

\begin{document}
\centerline{\it Physik auf dem Computer I}
\medskip
\centerline{\bf \"UBUNG 11} 
\medskip
\centerline{\it Pseudozufallszahlen und deren G\"ute}

\vspace{1.0cm}
Bitte protokollieren Sie Ihre Arbeit an diesem \"Ubungsblatt wieder durch
Beantwortung der Fragen. Vergessen Sie nicht, Ihre(n)
Namen auf dem Protokoll zu vermerken und {\it geben Sie dies am Ende der
\"Ubung Ihrem Assistenten.} Sollten Sie an keiner der
\"Ubungsgruppen teilnehmen k\"onnen, so senden Sie Ihre L\"osungen 
bis sp\"atestens zur n\"achsten Vorlesung per e-mail (reines ASCII Format,
bitte keine attachments).

\bigskip

{\bf Motivation.\ } \\
Wir wollen in dieser \"Ubung das Arbeitsprinzip kongruentieller 
Pseudozufallszahlengeneratoren verstehen und dann pr\"ufen,
inwiefern die gelieferten Zahlen wirklich ``zuf\"allig'' sind. 
Wir werden dazu die Verteilung der produzierten Zufallszahlen
verschiedener Generatoren vergleichen.

% Sie finden ein vorbereitetes Programm im Verzeichnis \\
% {\tt /user0/sts/COMPUTERPHYSIK/BLATT12}. \\
% Tippen Sie jetzt in ihrer Kopie des 
% Verzeichnisses {\tt make,} um ein Programmger"ust {\tt ran} zu
% erzeugen, das 5 verschiedene Zufallszahlengeneratoren realisiert, 
% die wir auf ihre G"ute hin genauer untersuchen wollen. 
% Falls Sie steckenbleiben sollten, so enth\"alt die
% Datei \verb|ranx.cc| einen L"osungsvorschlag zur Beantwortung
% der unten gestellten Fragen. 
% Das Beispielprogramm erzeugt mit f"unf verschiedenen Zufallszahlengeneratoren
% jeweils $10^5$ Werte und berechnet die Wahrscheinlichkeitsverteilungsfunktion.
% Wir wollen die Zufallszahlen auf Mittelwert, Varianz und Korrelationen 
% pr\"ufen. 

\bigskip

{\bf Aufgabe 1.\ }  Kongruentielle Generatoren.\\
(i) Eine wichtige Klasse von Zufallszahlengeneratoren zur Erzeugung 
von Pseudozufallssequenzen beruhen auf 
wiederholter Multiplikation der jeweils letzten generierten 
Pseudozufallszahl $z_n$ mit einer Zahl $m$, 
m\"oglicher Addition einer Zahl $a$ und dann der Restbildung 
mit einer weiteren Zahl $r$, die gleichzeitig eine obere Schranke 
f\"ur die erzeugten Zahlen darstellt 
\begin{equation}
	z_{n+1} = (m z_n + a)\  \mbox{mod}\  r.
\end{equation} 
Da bei der Restbildung mit $r$ nur $r$ verschiedene Zahlen auftreten
k\"onnen, ist auch die maximale Sequenzl\"ange des Generators gleich $r$.  
Die Wahl von $m$ und $r$ ist wichtig f\"ur die  Qualit\"at der
Generatoren. W\"ahlen Sie z.B. $r=13$ aus und \"uberzeugen Sie
sich, da\ss{} Sie die maximal m\"ogliche Periodenl\"ange des
``Zufallszahlengenerators'' erhalten, wenn Sie $(m,a,r) = (1,1,13)$ w\"ahlen.  
Ermitteln sie die Periodenl\"angen f\"ur alle m\"oglichen sinnvollen
$m$ bei gleichem $a=1$!\\
(ii) Wie beeinflu\ss{}t der Wert von $a$ die Periodenl\"ange---
z.B. f\"ur $m=7$ und $m=4$?\\
(iii) {\it (freiwillig)}\\
In {\it Numerical Recipes,} einem Standardwerk der Computerphysik, wird f\"ur
einen einfachen Generator  $(m,a,r) = (4561,51349,243000)$ empfohlen.
Der Wert f\"ur $r$ scheint klein zu sein. Welchen Vorteil hat dieser 
Generator gegen\"uber solchen, bei denen $r$ in der Gr\"o\ss{}enordnung 
$2^{31}$ liegt, was ist der Nachteil? 


\bigskip

{\bf Aufgabe 2.\ } Gleichverteilung\\
Wir wollen die Qualit\"at der Gleichverteilung der von
verschiedenen Generatoren gelieferten Zufallszahlen beurteilen.
Teilen Sie dazu das vom Zufallszahlgenerator abgedeckte Interval
$0\dots r-1$ in $n_I=100$ Teilintervalle 
$i*(r-1)/n_I..(i+1)*(r-1)/n_I,\ i=0,\dots,\ n_I-1$  
auf und ermitteln sie f\"ur jedes Teilintervall $i$ die Anzahl $N_i$ der 
bei insgesamt $N$ ``Ziehungen'' hineinfallenden Pseudozufallszahlen.
Der Mittelwert $\langle N_i\rangle$ \"uber alle Intervalle betr\"agt 
$Np = N*(1/n_I)$ liegt, wobei $p$
hier die 'a priori' f\"ur alle Teilintervalle gleiche
``Trefferwahrscheinlichkeit'' $(1/n_I)$  bezeichnen soll.  

(i) Tragen Sie f\"ur $N>=10^6$ und den Generator aus Aufgabe (1.iii) die 
$N_i$ mittels \verb|gnuplot| gegen $i$ auf. Vergleichen Sie mit 
dem Resultat f\"ur einen Kirkpatrick-Stoll Generator (EXOR basiert), den 
Sie fertig programmiert in \verb|PTSRandom.h| und \verb|PTSRandom.cc| in 
\verb|~sts/COMPUTERPHYSIK/BLATT12| finden und in der folgenden Weise 
benutzen k\"onnen:
\begin{verbatim}
#include "PTSRandom.h"

int main(){
  // Kirkpatrick Stoll generator with seed 2345
  PTS_KPS250RNG rng(2345);  
  // max value of the produced unsigned integers 
  // this value can actually occur in the sequence
  unsigned  int max = rng.UnsignedMax();
  unsigned  int rnd;
  // every call to Unsigned() produces a pseudorandom number 	
  rnd  = rng.Unsigned();    
}
\end{verbatim}
Kompilieren Sie z.B.\ mit \verb|g++ example.cc PTSRandom.cc|.
Welche Unterschiede finden sie zwischen den Generatoren (Skala beachten)? \\
(ii) Falls unsere Generatoren wirklich ``zuf\"allige'' Sequenzen 
liefern, dann k\"onnen wir auch die Streubreiten der $N_i$ aus der
Binominalverteilung bestimmen (hier sei $q\equiv 1-p$ und $P(N_i)$ die
Wahrscheinlichkeit, im Interval $i$ genau $N_i$ Zahlen zu finden),
\begin{equation}
  P(N_i) = \left(\begin{array}{c} N\\ N_i \end{array}\right) p^{N_i}q^{N-N_i},
\end{equation}
die f\"ur gro\ss{}e $N$ \"ubergeht in eine Gau\ss{}verteilung
\begin{equation}
  P(N_i) = \frac{1}{\sqrt{2\pi Npq}}e^{-\frac{N_i - Np}{2Npq}}.	
\end{equation}
mit der Varianz $\sigma^2 = Npq \approx Np.$ Vergleichen Sie diese 
mit dem empirischen Wert    
\begin{equation}
\sigma^2 = \langle N_i^2 \rangle - \langle N_i \rangle ^2 
	\approx \frac{1}{n_I} \sum_i^{n_I} ( N_i - Np )^2.   	
\end{equation}
Was l\"a\ss{}t sich daher \"uber die beiden verglichenen Generatoren 
aussagen?

\bigskip

{\bf Aufgabe 3.\ (freiwillig) }
Ein statistischer Test, den viele kongruentielle 
Zufallszahlengeneratoren nicht 
bestehen, ist der sogenannte $n$-tupel Test - hier sei $n=3.$
In diesem  Falle werden Tripel von aufeinanderfolgenden Zahlen 
gebildet. Falls diese unabh"angig voneinander sind, so sollten sie 
ein dreidimensionales, w"urfelf"ormiges Volumen ``gleichm"a"sig'' 
ausf"ullen. Stellen wir uns z.B. einen W"urfel aus $30^3$
Einheitsw"urfeln zusammengesetzt vor. Einen dieser Einheitsw"urfel
k"onnen wir mit einem Tripel addressieren, das wir aus drei mit
geeigneten Faktoren multiplizierten Zufallszahlen zusammensetzen. 

\smallskip \  Schreiben Sie ein Programm/Unterprogramm,
das als Funktion der erzeugten Tripel $t$ die Anzahl $n_{\rm e}(t)$ der 
verbleibenden {\it nichtbesetzten} Einheitsw"urfel bestimmt. Vergleichen 
Sie die Ergebnisse f"ur die Generatoren mit der Funktion 
\begin{equation}
  n_e(t) = n_e(0) e^{-t/n_e(0)}.
\end{equation}
 
\vfill
\begin{flushright}
\begin{tabular}{lll}
Michael Brunner & Di 9:45 & {\tt michi@ica1.uni-stuttgart.de}\\
Stefan Schwarzer & Di 11:30 & {\tt sts@ica1.uni-stuttgart.de} 
\end{tabular}
\end{flushright}


\end{document}

