Spielcomputer

Seit 2002 veranstaltet der Entropia e.V. in Karlsruhe jährlich die Gulaschprogrammiernacht, das ist ein mehrtägiger Kongress, wo Nerds, Häcksen und Maker ihre Projekte vorstellen, Erfahrungen austauschen und Vorträgen lauschen. Die GPN15 fand Anfang Juni 2015 im ZKM und der HfG Karlsruhe statt, und zog diesmal auch Mathe-Begeisterte an: Florian Gilges ist mit dem Life Science Lab als Schüler nach Karlsruhe gekommen, und will unter anderem Näherungen an die Kreiszahl $\pi$ effizient berechnen. Dazu baut er sich einen eigenen Computer. Im Gespräch mit Sebastian Ritterbusch erklärt er uns, wie er dazu logische Gatter aus rotem Erz baut.

Zunächst ist die Kreiszahl $\pi$ (Pi) als das Verhältnis von Umfang zu Durchmesser eines beliebigen Kreises definiert und ermöglicht uns mit der Formel $A=\pi r^2$ auch aus dem Radius $r$ die Fläche $A$ eines Kreises zu berechnen. Da Pi jedoch eine sogenannte irrationale und transzendente Zahl ist (d.h. dass nach dem Komma unendlich viele Stellen folgen, die keine Wiederholung aufweisen), lässt sich der Wert nie exakt angeben.

Um nun eine Näherung für Pi zu berechnen, lassen sich verschiedene Verfahren verwenden: Ein Kreis wird gezeichnet und Umfang und Durchmesser gemessen, das Verhältnis ist dann eine Näherung an Pi. Eine andere Möglichkeit ist die Berechnung durch eine Winkelfunktion: Der Arkustangens hat bei 1 den Wert $\pi /4$. Nimmt man also die Taylorentwicklung des Arkustangens mit x=1 und multipliziert mit 4, erhält man Pi. Neben der (von der Konvergenzgeschwindigkeit) relativ ineffizienten Taylor-Reihe gibt es noch viele weitere Verfahren, die ebenfalls Pi annähern.

Die Berechnung will Florian in Minecraft durchführen, und baut sich dafür einen Rechner innerhalb dieses Spiels. Aber wie kann ein einfaches Spiel so etwas bieten? Schließlich ist Minecraft nur eine Nachahmung unserer Welt mit ganz natürlichen Ressourcen. So bietet eine Minecraft-Welt verschiedene Vegetations- und Klimazonen und verschieden Landschaften und Umgebungen, wie z.B. Laubwälder, Nadelwälder, Steppen, Wüsten, Schneegebiete, uvm. Es gibt jedoch auch Stoffe, die es in unserer Welt nicht gibt: Einer davon ist Redstone. Dieser besondere Stoff kann in Höhlen tief unter der Erde als Erz gefunden werden und gibt abgebaut ein Pulver, das ähnliche Eigenschaften, wie elektrische Leitungen hat.

Aus Redstone-Pulver und weiteren Materialien, die man in der Welt findet, lassen sich Logikelemente bauen: Inverter, Verstärker, Verzögerer und Vergleicher. Diese Basiselemente können vom Spieler in die Welt gebaut und zu großen Schaltungen zusammengesetzt werden. Angefangen bei einfachen Speichern und Signalstärkespeichern (Redstone-Energie hat 16 Stufen von 0 bis 15), bis hin zu Logikgattern, wie UND-Gatter, XOR-Gatter und Flip-Flops. Kurzum lassen sich mit den Basiselementen alle Komponenten für einen Computer zusammenstellen, aber auch einfachere Dinge, wie Code-Schlösser und Tür-Steuerungen sind möglich.

Doch so einfach, wie es nun erscheint, ist es nicht, denn jedes Basiselement hat eine Verzögerung von mindestens einer Zehntel- bis vier Zehntelsekunden. Das bedeutet, dass der Computer sehr langsam wird und Berechnungen sehr aufwendig werden. Deshalb ist Optimierung sehr wichtig, indem an jeder Stelle die Bauteile effizienter gemacht werden und die Mathematik zur Berechung ebenfalls (für den Computer) effizienter gestaltet wird. Hier konnte Florian das XOR-Gatter und den Programm-Zähler aus Halbaddierern und Volladdierern durch intelligente Kniffe deutlich beschleunigen. Eine weitere Möglichkeit besteht auch in der Nutzung von redundanten Binärdarstellungen, die bei einer großen Anzahl von Additionen große Geschwindigkeitsvorteile bringen können.

Neben der Optimierung der Hardware ist auch die Optimierung der Software wichtig, was zur Mathematik zurückführt: Berechnungen wie Multiplikationen, Potenzen oder Wurzeln sind auf Logikebene komplizierte Operationen, auch wenn unsere Taschenrechner die Aufgaben in Sekundenbruchteilen lösen. Der einfachste Weg für die Multiplikation ist, dass man eine Additionskette bildet: $3·4=3+3+3+3=4+4+4$. Führt man dieses Verfahren mit größeren Zahlen durch, wächst der Aufwand linear. Ein anderes Verfahren ist die schriftliche Multiplikation, aber es geht noch effizienter: Die Russische Bauernmultiplikation. Mit etwas Übung lassen sich so, wenn gerade kein Taschenrechner da ist, auch große Zahlen multiplizieren. Für den Computer sind jedoch beide Verfahren durch das Binärsystem äquivalent.

Komplizierter sind dann schon Wurzeln. Diese lassen sich nicht so leicht berechnen, wie eine Addition oder Multiplikation. Ein mögliches Näherungsverfahren ist das Heron-Verfahren. Es gibt jedoch auch das schriftliche Wurzelziehen, das im Binärsystem leicht zu implementieren ist. Florian hat sich diese Techniken aus Videos wie dem Youtube-Kanal Schoolseasy selbst angelernt.