Abschnittsübersicht

    • Was sind Pseudo-Zufallszahlen?

      Ein Mikrocontroller ist ein äußerst kompakter Computer, der dazu geschaffen wurde, vordefinierte Abläufe, auch Programme genannt, auszuführen. In diesem Prozess ist das Ergebnis jedes Rechenschritts deterministisch, das heißt, vorhersehbar.

      Wenn jedoch jeder Rechenschritt vorhersehbar ist, wie können dann zufällige Zahlen erzeugt werden? Die kurze Antwort lautet: Das ist nicht möglich! Deswegen werden stattdessen sogenannte Pseudozufallszahlen berechnet. Diese Zahlen wirken zufällig, obwohl ihnen eine vergleichsweise einfache Berechnung zugrunde liegt. Nehmen wir ein Beispiel:

      1, 2, 3, 4, 5, 6, 1, 2, ... 

      Diese Zahlenfolge kann zufällig sein, wirkt jedoch berechenbar. Es folgt immer die nächstgrößere Zahl auf dem Würfel. Nach der Zahl 6 startet die Folge wieder von vorne. Im Gegensatz dazu steht diese Abfolge:

      1, 3, 4, 6, 2, 2, 5, 1, ... 

      Hier fällt es schwer, ein Muster zu erkennen. Entsprechend lässt sich die nächste Zahl nicht vorhersagen - und genau so funktionieren Pseudozufallszahlen.

    • Berechnung von Pseudo-Zufallszahlen

      Die Berechnung von Pseudo-Zufallszahlen kann auf viele unterschiedliche Wege erfolgen. In diesem Kurs wird der sogenannte Lineare Kongruenzgenerator beschrieben, da dieser auch auf dem Mikrocontroller im Bausatz implementiert wurde. 

      Lass dich vom Namen nicht abschrecken, denn die dahinterliegende mathematische Funktion eines linearen Kongruenzgenerators ist eigentlich ziemlich einfach. Betrachten wir zunächst ein konkretes Beispiel:

      \( seed_{0} = 0 \)

      \( seed_{i+1} = 4 \cdot seed_i + 3 \)

      In diesem Beispiel haben wir einen Startwert \(seed_0\) von 0 und eine Berechnungsvorschrift für alle darauf folgenden Zufallswerte. Wichtig ist hierbei zu verstehen, dass der nächste Zufallswert \(seed_{i+1}\) immer vom vorherigen Wert \(seed_i\) abhängt.

      Mit der Berechnungsvorschrift können jetzt beliebig viele Werte ermittelt werden. Nachfolgend findest du die ersten 10 Zufallszahlen der Folge:

      \( seed_{0} = 0 \)

      \(seed_{1} = 4 \cdot seed_{0} + 3 = 4 \cdot 0 + 3 = 3\)

      \(seed_{2} = 4 \cdot seed_{1} + 3 = 4 \cdot 3 + 3 = 15\)

      \(seed_{3} = 4 \cdot seed_{2} + 3 = 4 \cdot 15 + 3 = 63\)

      \(seed_{4} = 4 \cdot seed_{3} + 3 = 4 \cdot 63 + 3 = 255\)

      \(seed_{5} = 4 \cdot seed_{4} + 3 = 4 \cdot 255 + 3 = 1023\)

      \(seed_{6} = 4 \cdot seed_{5} + 3 = 4 \cdot 1023 + 3 = 4095\)

      \(seed_{7} = 4 \cdot seed_{6} + 3 = 4 \cdot 4095 + 3 = 16383\)

      \(seed_{8} = 4 \cdot seed_{7} + 3 = 4 \cdot 16383 + 3 = 65535\)

      \(seed_{9} = 4 \cdot seed_{8} + 3 = 4 \cdot 65535 + 3 = 262143\)

      \(seed_{10} = 4 \cdot seed_{9} + 3 = 4 \cdot 262143 + 3 = 1048575\)

    • Berechnung von Pseudo-Zufallszahlen - Fallbeispiel Würfel

      Im vorherigen Abschnitt hast du einen allgemeinen linearen Kongruenzgenerator kennengelernt. Dieser hat immer größer werdende Werte berechnet. Im Falle unseres Würfels ist dies ein Problem, da wir lediglich Werte von 1 und 6 benötigen. Dafür wird eine weitere Rechenoperation benötigt: Die Division mit Rest, oder auch Modulo.

      Betrachten wir beispielsweise mal Modulo 10, geschrieben % 10. Dann ergeben sich folgende Rechenergebnisse:

      \( 9 \% 10 = 9 \)

      \( 14 \% 10 = 4 \)

      \( 108 \% 10 = 8 \)

      \( 10 \% 10 = 0 \)

      Für unseren Würfel können wir später einfach Modulo 6, geschrieben % 6, verwenden. Dies resultiert in Werte von 0 - 5. Um noch einen Minimalwert von 1 zu erhalten, müssen wir 1 addieren. Insgesamt lautet die allgemeine Rechenvorschrift für einen Zufallsgenerator für Würfel-Werte:

      \(seed_{i+1} = (multiplier \cdot seed_i + increment) \% 6 + 1\)

      Die Werte für \(multiplier\) sowie \(increment\) können beliebig gewählt werden. Für folgendes Beispiel wählen wir, wie im letzten Abschnitt auch, \(multiplier = 4\) und \(increment = 3\). Mit einem Startwert von 0 ergeben sich somit folgende erste 10 Zahlen der Folge:

      \(seed_{0} = 0\)

      \(seed_{1} = 4 \cdot seed_{0} + 3 = 4 \cdot 0 + 3 = 4\)

      \(seed_{2} = 4 \cdot seed_{1} + 3 = 4 \cdot 4 + 3 = 2\)

      \(seed_{3} = 4 \cdot seed_{2} + 3 = 4 \cdot 2 + 3 = 6\)

      \(seed_{4} = 4 \cdot seed_{3} + 3 = 4 \cdot 6 + 3 = 4\)

      \(seed_{5} = 4 \cdot seed_{4} + 3 = 4 \cdot 4 + 3 = 2\)

      \(seed_{6} = 4 \cdot seed_{5} + 3 = 4 \cdot 2 + 3 = 6\)

      \(seed_{7} = 4 \cdot seed_{6} + 3 = 4 \cdot 6 + 3 = 4\)

      \(seed_{8} = 4 \cdot seed_{7} + 3 = 4 \cdot 4 + 3 = 2\)

      \(seed_{9} = 4 \cdot seed_{8} + 3 = 4 \cdot 2 + 3 = 6\)

      \(seed_{10} = 4 \cdot seed_{9} + 3 = 4 \cdot 6 + 3 = 4\)

      Hier siehst du auch direkt schon einen Nachteil von pseudo-Zufallszahlen: Wenn die Werte der Berechnungsvorschrift ungünstig gewählt wurden, dann wiederholt sich die Zahlenfolge. Obiges Beispiel resultiert in

      4, 2, 6, 4, 2, 6, 4, 2, 6, ...

      wodurch die Berechnung wieder absolut vorhersehbar ist. Einige Zahlenwerte, wie z.B. 1, 3 und 5 werden nie erreicht. Für die Implementierung auf dem Mikrocontroller wurden deshalb möglichst große und unterschiedliche Werte gewählt, da so möglichst viele verschiedene Zufallszahlen entstehen, ohne dass sie sich wiederholen.