Letzte Woche haben wir gelernt, dass Zufall im Computer meistens aus einer einzigen "Startzahl" generiert wird, das ist der so genannte "Seed", auf Deutsch also "Samen". Aber wie kann man ausgehend von einer einzigen Zahl unendlich viele weitere Zahlen erzeugen?

Und vor allem möchte man nicht irgendwelche Zahlen erzeugen. Es gibt ein paar Regeln an die man sich halten muss um von "gutem" Zufall sprechen zu können. Diese Regeln sind nicht für jeden Anwendungsfall genau gleich, man wird an einen Zufallszahlengenerator für einen Würfelsimulator vermutlich andere Anforderungen stellen als an einen Generator für kryptografische Signaturen zur Absicherung von Bankgeschäften. Um zu sehen was für eine Auswirkung verschiedene Regeln auf den Generator haben schauen wir uns mögliche Regeln für einen Würfelsimulator einfach mal an:

• Seedbasiert: Um den Generator zu starten brauchen wir genau eine beliebige Zahl.
• Fester Wertebereich: Jedes Ergebnis unseres Simulators soll eine Zahl zwischen 1 und 6 sein.
• Gleichverteilt: Wenn man den Simulator ausreichend lange laufen lässt, wir nehmen der Einfachheit halber einfach mal 36 generierte Zahlen, soll jede Zahl im Wertebereich gleich häufig auftreten.
• Unvorhersehbar Kein Ergebnis soll sich mit einem Blick auf die vorher generierten Zahlen einfach vorhersagen lassen, ohne dass man die Regel zum erzeugen der Zahlen kennt. Oder anders gesagt: Die Regel zur Erzeugung der Zufallszahlen soll sich nicht einfach ablesen lassen.

Mit diesen Regeln können wir uns jetzt ein paar Zufallszahlengeneratoren anschauen und diese auch bewerten: Eine sehr einfache Möglichkeit die Gleichverteilung und den Wertebereich einzuhalten ist es einfach immer Eins auf das vorige Ergebnis zu addieren und bei dem maximalen Wert einfach wieder mit dem minimalen Wert zu beginnen. Dieses Verfahren entspricht ungefähr der mathematische Funktion (x + 1) % 6, x ist dabei immer das Ergebnis des vorherigen "Wurfs". Das Prozentzeichen steht dabei für die Modulo-Operation, also den ganzzahligen Rest einer Division. 5 % 2 ergibt 1, 7 % 4 ergibt 3, 12 % 6 ergibt 0 ... Als Seed kann eine beliebige Zahl fungieren, wir schauen uns mal ein paar Beispiele an:

Seed	Serie
1	2,3,4,5,0,1,2,3,4,5,0, ...
4	5,0,1,2,3,4,5,0,1,2,3, ...
13	2,3,4,5,0,1,2,3,4,5,0 ...

Wir können zunächst festhalten, dass schon der Wertebereich nicht ganz eingehalten wird. Glücklicherweise können wir das sehr einfach heilen: Wir addieren einfach nochmal 1 auf das Ergebnis drauf. Durch den Modulo-Operator können wir mit beliebigen Zahlen Auch die Gleichverteilung ist gegeben: Bei 36 erzeugten Zahlen haben wir 6 Einsen, 6 Zweien, ... Problematisch ist natürlich die Vorhersehbarkeit: Es gibt nur 6 mögliche Serien, viel mehr als die beliebig großen Zahlen für Seeds vermuten lassen. Man könnte anstelle der obigen Funktion auch einfach mit der Sinusfunktion arbeiten. Dazu reicht die Formel |sin(x) * 5| wobei x in diesem Fall nicht das Ergebnis des vorherigen Wurfs ist, sondern der immer wieder um 1 erhöhte Seed. Und weil der Sinus auch negative Werte ausspuckt, müssen wir an dieser Stelle nochmal den Betrag  des Ergebnisses nehmen (im englischen spricht man von absolute value). Und schlussendlich arbeitet der Sinus natürlich nicht mit Ganzzahlen, wir müssen also noch runden (engl. round). Wenn man das Ganze in der Programmiersprache Haskell ausdrückt kommt dabei der folgende Code raus: sinusZufall x = round $ abs $ sin(x) * 5 Und weil wir das ganze nun programmiert haben, können wir das auch ohne Probleme mehrfach ausführen. In Haskell kann man dafür einfach map nehmen und sagen für welchen Zahlenbereich man unsere Funktion ausgeführt haben möchte: map sinusZufall [1..36] ruft die Funktion für alle Werte von 1 bis 36 auf.

Intervall	Serie
1..36	4,5,1,4,5,1,3,5,2,3,5,3,2,5,3,1,5,4,1,5,4,0,4,5,1,4,5,1,3,5,2,3,5,3,2,5
1000..1035	4,5,1,4,5,2,3,5,2,3,5,3,2,5,3,1,5,4,1,5,4,0,4,5,1,4,5,1,3,5,2,3,5,3,2,5
100..135	3,2,5,3,2,5,4,1,5,4,0,4,4,0,4,5,1,3,5,2,3,5,2,2,5,3,2,5,4,1,5,4,0,4,4,0

Auch hier müssen wir den Wertebereich durch Addition von 1 wieder ein bisschen anpassen. Dummerweise sind die Werte wohl nicht gleichverteilt, die 0 taucht in den ersten beiden Serien nur einmal auf, die 5 hingegen zwölf mal. Und weil die Werte schon nicht gleichverteilt sind ist eine Vorhersage natürlich zumindest in Teilen möglich. Und auch auf die mathematische Formel kann man ganz gut schließen, wenn man die Werte, wie im Titelbild zu sehen, einfach mal grafisch notiert. Mit einfacher Schulmathematik kommen wir an dieser Stelle also wohl nicht weiter ... Warum die Lösung trotzdem nicht ganz so kompliziert ist sehen wir dann nächste Woche. In der letzten Woche haben wir von auf Zeit basierenden Zufallszahlengeneratoren gehört. Und hier seid jetzt ihr gefragt: Schreibt dazu in den Kommentaren wie ihr aus der Zeit eine Serie von Zahlen generieren würdet und wie euer Ansatz zu den oben genannten Kriterien passt.