Viele Entwickler haben vom Ariane-5-Fehler gehört, einem der berüchtigtsten Softwarefehler in der Geschichte der Luft- und Raumfahrttechnik. Er ereignete sich am 4. Juni 1996 beim Jungfernflug der Ariane-5-Rakete, die vier Cluster-Satelliten zur Erforschung der Magnetosphäre der Erde in den Orbit bringen sollte.
Der Fehler selbst lag in der Software des Lenksystems der Rakete. Die Komponente, die einen 64-Bit-Gleitkommawert in eine vorzeichenbehaftete 16-Bit-Ganzzahl für das Lenksystem umwandeln sollte, löste wegen eines Überlaufs eine unbehandelte Ausnahme aus. Letztlich trug eine einzige Codezeile zu einem Ausfall bei, der Millionen von Dollar kostete und den Ariane-5-Start zu einem der teuersten Softwarefehler der Geschichte machte.
Doch kennen Sie auch eine Codezeile, die möglicherweise Millionen von Dollar wert war?
Es war diese berühmte C++-Zeile:i = 0x5f3759df - (i >> 1);
Diese Zeile tauchte erstmals im Quake-Code auf, um die Berechnung der inversen Quadratwurzel zu optimieren.
float Q_rsqrt(float number)
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y; // evil floating point bit level hacking
i = 0x5f3759df - ( i >> 1 ); // what the fuck?
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
return y;
}Warum ist die Optimierung der inversen Quadratwurzel so wichtig?
Inverse Quadratwurzeln werden in der Grafik von Videospielen häufig eingesetzt, insbesondere in 3D-Engines. Viele Bereiche der Spieleprogrammierung, etwa Wegfindung, Beleuchtung und Reflexionen, beruhen stark auf der Normalisierung von Vektoren, für die eine inverse Quadratwurzel benötigt wird. Die Berechnung inverser Quadratwurzeln, die Gleitkommadivisionen umfasst, kann für Prozessoren jedoch rechenintensiv sein. In schnellen und grafisch anspruchsvollen Spielen wie Quake III Arena werden solche Berechnungen millionenfach pro Sekunde ausgeführt. Schon eine kleine Leistungssteigerung konnte daher die Grafikverarbeitung deutlich beschleunigen und die Bildrate verbessern. Um die Rechenkosten der inversen Quadratwurzel zu vermeiden, entwickelten die Programmierer der id-Tech-3-Engine eine außergewöhnlich schnelle und zugleich genaue Näherung.
Ohne diese clevere Optimierung hätte Quake seinen Stellenwert als Referenz in der Spieleindustrie möglicherweise nicht erreicht.
Wer steckte hinter dieser genialen Lösung?
Rys Sommerfeldt, Senior Manager des European Game Engineering Teams bei AMD RTG, startete 2004 eineUntersuchungzur Herkunft der Funktion. Die Nachforschungen führten schließlich zu Greg Walsh als ihrem Urheber. Greg Walsh ist eine bedeutende Persönlichkeit der Computergeschichte. Er war bei Xerox PARC an der Entwicklung des ersten WYSIWYG-Textverarbeitungsprogramms („What You See Is What You Get“) beteiligt und half bei der Gründung von Ardent Computer. Dort arbeitete Greg eng mit Cleve Moler, dem Schöpfer von MATLAB, zusammen. Cleve war es auch, den Greg als Inspiration für die Fast-Inverse-Square-Root-Funktion bezeichnete.
Die Lehre daraus
Bei manchen Problemen lohnt es sich, sich Zeit zu nehmen und über den Tellerrand hinauszudenken. Das bedeutet, sich von konventionellen Denkmustern zu lösen und ungewöhnliche, innovative und kreative Lösungswege zu erkunden. Wenn ein Problem schwer zu lösen ist, betrachten Sie es in Ruhe aus verschiedenen Perspektiven. Vielleicht finden Sie eine Lösung, die Ihre Erwartungen übertrifft.