Section outline

    • 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:

      Kopf, Zahl, Kopf, Zahl, Kopf, Zahl, ... 

      Diese Zahlenfolge kann zufällig sein, wirkt jedoch berechenbar. Nach "Kopf" folgt immer "Zahl", nach "Zahl" tritt erneut das Ereignis "Kopf" ein. Im Gegensatz dazu steht diese Abfolge:

      Kopf, Kopf, Zahl, Kopf, Zahl, Zahl, ... 

      Hier fällt es schwer, ein Muster zu erkennen. Entsprechend lässt sich das nächste Ereignis 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 Münzwurf

      Im vorherigen Abschnitt hast du einen allgemeinen linearen Kongruenzgenerator kennengelernt. Dieser hat immer größer werdende Werte berechnet. Im Falle unseres Münzwurfs ist dies ein Problem, da wir lediglich Werte für "Kopf" und "Zahl" benötigen.

      Die Lösung dafür ist allerdings relativ simpel: Wir teilen unseren berechneten Wert durch den maximalen Wert, den der Zufallsgenerator erzeugen kann. Dadurch ergibt sich ein Wertebereich von 0 bis 1. Um nun einen fairen Münzwurf zu erstellen, wird der dividierte Wert mit 0.5 verglichen. Ist dieser kleiner als 0.5, dann ist das Ergebnis "Kopf", ansonsten "Zahl".