Als Kind der 90er saß ich viele Stunden vor Spielekonsolen oder dem PC. Ich verbrachte so manchen Nachmittag mit dem Fliehen vor der Polizei bei »Grand Theft Auto«, den Abenteuern von Lara Croft in »Tomb Raider« oder dem Skateboarden mit ikonischer Musik bei »Tony Hawk’s Pro Skater«. Ein anderes Spiel, das 1999 erschien, ging damals allerdings an mir vorbei: Quake 3. Es gilt als eines der besten Computerspiele seiner Zeit – und hat die Branche nachhaltig geprägt. Das lag weniger an der Story, die kaum vorhanden ist, sondern daran, dass Quake 3 einer der ersten Ego-Shooter auf Multiplayer-Basis war. Die Spieler konnten ihre Computer über Netzwerkkabel oder das Internet miteinander verbinden, um sich gegenseitig abzuschießen.

Das ist aber nicht der Grund, weshalb ich in dieser Kolumne über Quake 3 schreiben möchte. Sehr viel spannender als das Spiel an sich finde ich den Code, der dahintersteckt. Darin verbirgt sich nämlich eine kleine Sensation: ein extrem effizienter Algorithmus, der Fachleute bis heute staunen lässt und Fragen aufwirft.

Spieleentwickler hatten es in den 1990er-Jahren nicht leicht. Sie mussten mit der extrem geringen Rechenleistung der Computer zurechtkommen und daher ihre Spiele möglichst effizient codieren. Im Ego-Shooter Quake 3 bewegt sich der Spieler durch eine dreidimensionale Welt. Daher mussten sich die Programmierer überlegen, wie sie die 3D-Grafik und die zugehörigen Berechnungen möglichst clever umsetzen.

Ein Rechenschritt, der dabei immer wieder auftaucht, ist die Berechnung der inversen Quadratwurzel, also eins durch die Wurzel einer Zahl. Diese braucht man, um die Ausrichtungen von Objekten oder anderen Spielern im dreidimensionalen Raum zu untersuchen. Hierfür bastelt man quasi einen Pfeil, der die Ausrichtung anzeigt, einen sogenannten Vektor. Um diesen mit anderen Ausrichtungen – anderen Vektoren – vergleichen zu können, müssen die Pfeile gleich lang sein. Man muss also alle Vektoren auf dieselbe Länge skalieren. Und dafür braucht man die inverse Quadratwurzel.

Ein seltsamer Code

Wenn ich Sie jetzt bitten würde, ohne Taschenrechner die inverse Quadratwurzel von 26 zu berechnen, wären Sie wohl einige Zeit beschäftigt. Um ehrlich zu sein, wäre ich damit auch überfordert. So auch die Computer in den 90er-Jahren. Die Maschinen konnten zwar ein Ergebnis liefern, aber die Berechnung erforderte ziemlich viel Leistung. Ein Problem stellt dabei die Quadratwurzel dar, ein anderes die Division. Beide Rechenschritte verschlingen Ressourcen. Daher suchten die Programmierer von Quake 3 nach einer cleveren Möglichkeit, die inverse Quadratwurzel möglichst sparsam zu bestimmen. Und tatsächlich findet sich im Quellcode ein extrem ausgefallener Weg dafür.

Das Spannende an der Geschichte: Die Entwickler gingen mit ihrer Idee nicht hausieren. Die Methode wäre wohl niemals bekannt geworden, wäre nicht irgendwann der Programmcode von Quake 3 quelloffen zur Verfügung gestellt worden. Dieser weckte das Interesse von neugierigen Nerds. Als diese den Codeschnipsel zur Berechnung der inversen Quadratwurzel entdeckten, waren sie erst einmal ratlos. Es war schwer, die einzelnen Schritte nachzuvollziehen – und die zugehörigen Kommentare der Entwickler waren nicht wirklich hilfreich.

Inzwischen gibt es viele Erklärungen, die Schritt für Schritt durch den Programmcode führen. Dabei werden Besonderheiten der Programmiersprache C ausgenutzt. Zahlen werden etwa in Speicheradressen umgewandelt und diese dann manipuliert. Dies ist eine clevere Möglichkeit, um aufwendige Rechenoperationen wie die Division zu vermeiden. »Stellen Sie sich das so vor, als würden Sie im Laden ein falsches Etikett auf etwas kleben und damit den Angestellten täuschen – hier ist es dagegen die Programmiersprache C, die wir täuschen«, erklärt der Informatiker Daniel Harrington von der University of Toronto.

Aus mathematischer Sicht ist der Code schnell erklärt. Um die inverse Quadratwurzel zu bestimmen, wird zunächst ein Ergebnis geraten (das natürlich nicht korrekt ist). Anschließend wird es durch ein festgelegtes Verfahren verändert. So nähert man sich schrittweise einer besseren Lösung.

All das ist weder bahnbrechend noch neu. Was jedoch beeindruckend ist: Für gewöhnlich sind vier bis fünf Wiederholungen des Verfahrens nötig, bis das Ergebnis nahe genug an einer tatsächlichen Lösung ist. Das erfordert viel Rechenleistung. Bei Quake 3 wurde der Startwert – also das geratene Ergebnis im ersten Schritt des Verfahrens – so clever gewählt, dass nur ein einzelner Optimierungsschritt nötig ist. Daher auch der letzte Kommentar »2nd iteration, this can be removed«: keine zweite Iteration nötig.

Eine magische Zahl

Die Optimierungsschritte entsprechen dem sogenannten Newton-Verfahren, das Nullstellen von Funktionen schrittweise annähert. Das mag zunächst abwegig klingen, schließlich möchte man die inverse Quadratwurzel berechnen und nicht irgendeine Nullstelle. Deswegen greifen die Programmierer auf einen Trick zurück: Sie definieren die anzunähernde Funktion als die Abweichung zwischen dem Näherungswert und dem realen Ergebnis. Durch das Newton-Verfahren wird der Fehler also immer kleiner, sodass man immer dichter an die exakte Lösung herankommt.

In der Praxis funktioniert das so: Angenommen, Sie möchten die inverse Quadratwurzel von 2,5 berechnen. Der Algorithmus geht in diesem Fall von einem gewissen Startwert aus – sagen wir 3,1 – , der als erste geratene Lösung angesetzt wird. Um die Abweichung zur tatsächlichen Lösung zu ermitteln, quadriert man den Startwert und dividiert eins durch das Ergebnis. Denn falls 3,1 wirklich die inverse Quadratwurzel von 2,5 wäre, dann müsste das Ergebnis von 1 durch 3,1² exakt 2,5 ergeben. In Wahrheit lautet das Ergebnis 0,10, liegt also weit daneben. Die Abweichung beträgt demnach 2,4.

Durch das Newton-Verfahren lässt sich diese reduzieren – je mehr Iterationen man durchführt, desto näher rückt man an den exakten Wert. In der Regel sind vier bis fünf solcher Schritte nötig, um bei einem verlässlichen Ergebnis zu landen. Quake 3 hat die Anzahl der benötigten Iterationen jedoch auf ein beeindruckendes Minimum gesenkt.

»Woher kommt dieser Wert, und wieso funktioniert der Code?«Chris Lomont, Informatiker

Grund dafür ist die Art und Weise, wie der Startwert für die Newtonschritte berechnet wird. Hierfür operiert der Algorithmus im Wesentlichen in drei Schritten:

1. Man nehme die übergebene Zahl, deren inverse Quadratwurzel berechnet werden soll, und wandelt diese in die zugehörige Speicherplatzadresse um.

2. Diese wird halbiert und vom Hexadezimalwert 0x5f3759df abgezogen. Das ist der Startwert für das Newton-Verfahren.

3. Anschließend wird ein Newtonschritt durchgeführt.

Besonders mysteriös erscheint dabei die kryptische Zeichenfolge 0x5f3759df, die inzwischen als »magische Zahl« in die Geschichte der Informatik eingegangen ist. Sie ist der Grund, warum nur eine Iteration notwendig ist, um eine Näherungslösung für die inverse Quadratwurzel zu erhalten, die höchstens einen Fehler von 0,175 Prozent erzeugt.

Sobald der Programmcode quelloffen verfügbar war, rätselten Fachleute über die Herkunft der magischen Zahl, darunter der Informatiker Chris Lomont, der in einem 2003 erschienenen Fachaufsatz schrieb: »Woher kommt dieser Wert, und wieso funktioniert der Code?«

Die Hexadezimalzahl 0x5f3759df entspricht 1 597 463 007 in Dezimalschreibweise. Indem Lomont die einzelnen Schritte des Programmcodes aufdröselte, erkannte er, dass sich 1 597 463 007 durch folgende Berechnung ergibt: $\frac{3}{2}\cdot 2^{23}\cdot (127–0,0450465)$. Die Werte ³/₂, 2²³ und die 127 ergeben sich durch die Umwandlung der Zahlendarstellungen in C. Spannend ist aber 0,0 450 465: Woher kommt diese Zahl?

Auf der Jagd nach dem Ursprung der rätselhaften Zahl

Das hat Lomont genauer unter die Lupe genommen. Er hat mathematisch untersucht, welcher Wert ein optimales Ergebnis für verschiedene Eingaben liefert. Sprich: Welcher Startwert nähert die inverse Quadratwurzel am besten an und sollte demnach zum kleinsten Fehler führen? Er kam dabei auf einen Wert von 1 597 465 647, der etwa $\frac{3}{2}\cdot 2^{23}\cdot (127–0,04483)$ entspricht. Das Ergebnis ist recht nahe an den Werten, die im Quellcode von Quake 3 zu finden sind.

Als Lomont seine Resultate mit denen des Originals verglich, stieß er auf eine Überraschung. Bei zwei Schritten des Newton-Verfahrens erwies sich seine berechnete Konstante tatsächlich als besser: Der größtmögliche Fehler fiel kleiner aus als mit dem Wert im Originalcode. »Doch mein Ergebnis weist nach einer Newton-Iteration einen größeren maximalen Fehler auf«, schreibt Lomont. »Das wirft erneut die Frage auf: Wie wurde die ursprüngliche Konstante abgeleitet?«

Bei seiner Berechnung hatte der Informatiker nur beachtet, welche Zahl den theoretisch bestmöglichen Wert liefern würde – und ließ dabei die Anzahl der Newtonschritte außer Acht. »Aus Neugierde habe ich nach einer besseren Konstante gesucht«, schreibt Lomont. Er wiederholte seine Berechnung und optimierte auf die bestmögliche Lösung für einen einzigen Newtonschritt. Er kam hierbei auf einen Wert von 1 597 463 174, was ungefähr 3/2⋅2²³⋅(127–0,045 033) entspricht. Als er dieses Ergebnis einem Praxistest unterzog, lieferte es tatsächlich leicht bessere Resultate als die magische Zahl im Quake-3-Code.

»Die neue Konstante 0x5f375a86 scheint etwas besser zu funktionieren als die ursprüngliche. Da es sich bei beiden um Annäherungswerte handelt, funktionieren beide in der Praxis gut«, schließt Lomont seine Analyse. »Ich würde gerne den ursprünglichen Autor finden, wenn möglich, und herausfinden, ob die Methode abgeleitet oder nur geraten und getestet wurde.« Wer das Internet kennt, kann sich vorstellen, dass die Community hartnäckig nach dem Urheber suchte, um eine Antwort auf Lomonts Frage zu finden.

Besonders engagiert war dabei der Informatiker Rys Sommefeldt, der sich zuerst an den Hauptentwickler von Quake 3, John Carmack, wandte. Der wusste jedoch auch nicht genau, wo dieser Codeabschnitt herkam, und konnte nur Vermutungen anstellen.

Ich erspare Ihnen alle Zwischenschritte dieser langwierigen Spurensuche: Die bekanntesten Entwickler der 90er-Jahre spielten sich gegenseitig den Ball zu, ohne dass sich jemand als Urheber meldete. Inzwischen scheint es so, als habe der Entwickler Greg Walsh, der Ende der 1980er-Jahre beim Computerhersteller Ardent Computer beschäftigt war, die magische Zahl in den Algorithmus der inversen Quadratwurzel eingeführt. Sie fand dann offenbar über mehrere andere Personen schließlich ihren Weg in den Quake-3 Algorithmus. Aber wie genau die magische Zahl bestimmt wurde, ist bis heute unklar.

Das ist kein besonders zufriedenstellendes Ende, ich weiß. Trotzdem finde ich die Geschichte des Quake-3-Algorithmus (oder besser: des Teils, der sich um die inverse Quadratwurzel dreht) extrem spannend. Denn es ist erstaunlich, wie viel Mühe und Hirnschmalz damals in die effiziente Programmierung von Software geflossen ist – ein Trend, der mit der heute verfügbaren Rechenleistung kaum noch vorhanden ist. Schade eigentlich.