Evil Bit Hack: Die magische Zahl 0x5f3759df

In der Geschichte der Computerspiele und der Computergrafik gibt es wenige Code-Snippets, die so legendär geworden sind wie die Funktion zur schnellen Berechnung der inversen Quadratwurzel aus dem Quellcode von Quake III Arena. Im Zentrum steht die hexadezimale Konstante 0x5f3759df und die berĂĽhmten Kommentare „evil floating point bit level hacking“ und „what the fuck?“.

Dieser Trick, oft als „Evil Bit Hack“ oder „Fast InvSqrt“ bezeichnet, ermöglichte es Ende der 1990er-Jahre, eine der teuersten Operationen in 3D-Spielen – die Normierung von Vektoren – drastisch zu beschleunigen.

In der 3D-Grafik ist die Berechnung von Flächennormalen unverzichtbar. Eine Flächennormale ist der Einheitsvektor, der senkrecht auf einer Oberfläche steht. Er wird unter anderem für Beleuchtungseffekte, Reflexionen und Kollisionserkennung benötigt. Die Länge eines Vektors v = (x, y, z) ergibt sich aus dem Satz des Pythagoras:

Um den Vektor zu normalisieren (also auf die Länge 1 zu bringen), teilt man jede Komponente durch diese Länge – was mathematisch der Multiplikation mit

entspricht. Die Berechnung der Quadratwurzel und der anschließenden Division war auf den Prozessoren der späten 1990er-Jahre vergleichsweise teuer. Lookup-Tabellen halfen, waren aber oft langsamer oder ungenauer als der folgende Hack.

Als id Software 2005 den Quellcode von „Quake III Arena“ (1999) freigab, stieĂź die Community auf diese Funktion (leicht bereinigt):

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;
}

Die Funktion liefert eine Näherung fĂĽr 1/sqrt{x}. Mit nur einer Newton-Iteration erreicht sie einen maximalen relativen Fehler von etwa 0,175 % – fĂĽr Beleuchtungsberechnungen völlig ausreichend.

IEEE-754-Gleitkommazahlen (32 Bit) bestehen aus Vorzeichenbit, Exponent (8 Bit, Bias 127) und Mantisse (23 Bit). Interpretiert man die Bits einer positiven Float-Zahl als Integer, erhält man eine grobe Approximation des Logarithmus der Zahl. Das ist der Schlüssel.

i = 0x5f3759df - (i >> 1); entspricht einer schnellen Näherung von -1/2 * log2(x) im Bit-Raum. Der Rechts-Shift (>> 1) halbiert den Integer-Wert und damit näherungsweise den Logarithmus. Die magische Konstante 0x5f3759df entsteht aus der Umformung der IEEE-754-Darstellung und einer Korrektur des Fehlers, der durch die Linearisierung des Logarithmus entsteht. Nach der Rückinterpretation der Bits als Float erhält man einen Startwert, der bereits relativ gut ist.

Anschließend verbessert eine Newton-Iteration die Näherung:

Das ist genau die Zeile mit „threehalfs“. Eine zweite Iteration wäre möglich, wurde aber im Original aus PerformancegrĂĽnden weggelassen. Der Beyond3D-Artikel von Rys Sommefeldt enthält eine interaktive Grafik, der die Arbeitsweise verdeutlicht.

Lange galt der Trick als Erfindung von John Carmack. Er selbst dementierte das. Die Spur führte über Gary Tarolli (3dfx, SGI) und andere zurück zu Greg Walsh. Walsh entwickelte den Algorithmus Ende der 1980er-Jahre bei Ardent Computer für die Titan-Grafikmaschine, inspiriert von Cleve Moler (Mitbegründer von MathWorks und Schöpfer von MATLAB). Die grundlegende Idee der Bit-Manipulation für Wurzeln geht sogar auf Arbeiten von William Kahan und K. C. Ng an der University of California, Berkeley, aus dem Jahr 1986 zurück.

Der Code wanderte ĂĽber verschiedene Firmen und Spiele (unter anderem eine Variante in „Interstate ’76“) und landete schlieĂźlich bei id Software.

Mit speziellen Hardware-Instruktionen wie „rsqrtss“ (SSE) oder entsprechenden GPU-Befehlen ist der Hack auf modernen Systemen meist ĂĽberflĂĽssig und oft sogar langsamer als die nativen Funktionen. Dennoch bleibt er ein klassisches Beispiel fĂĽr elegante Bit-Level-Optimierung, das Verständnis von IEEE-754 und die Kreativität, die nötig war, als jede Taktzyklus-Zählung zählte.

Der „Evil Bit Hack“ zeigt, wie tiefgreifendes Wissen ĂĽber die interne Darstellung von Zahlen und numerische Verfahren zu einem der bekanntesten und faszinierendsten Code-StĂĽcke der Spielebranche fĂĽhren konnte – und warum ein simpler Kommentar wie „what the fuck?“ Generationen von Programmierern in seinen Bann gezogen hat.

Quellen

Volker Zota: Zahlen, bitte! 0x5f3759df – merkwürdige Mathematik im Egoshooter. heise online, 17.05.2016
Wikipedia: Fast inverse square root
Beyond3D-Artikel von Rys Sommefeldt zur Herkunft des Algorithmus (2006/2007), zusammengefasst u. a. in:https://www.swarchitect.net/en/history-fast-inverse-sqrt/

Charles McEniry: The Mathematics behind the Fast Inverse Square Root Function Code (PDF)

YouTube: The Fast Inverse Square Root — 0x5f3759df explained!!, LearningTwice

 

Veröffentlicht unter Retro