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 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) als das Verhältnis von Umfang zu
Durchmesser eines beliebigen Kreises definiert und ermöglicht uns
mit der Formel auch aus dem Radius die Fläche 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 . 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: . 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.