Schnelle inverse Quadratwurzel

Schnelle inverse Quadratwurzel ist ein Algorithmus, der ${\dfrac {1} {\sqrt{x}}}$ , den Kehrwert (oder die multiplikative Inverse) der Quadratwurzel einer 32-Bit-Gleitkommazahl x im IEEE 754-Gleitkommaformat, schätzt. Die Berechnung reziproker Quadratwurzeln ist in vielen Anwendungen erforderlich, z. B. bei der Vektornormalisierung in Videospielen, und wird hauptsächlich für Berechnungen in der 3D-Programmierung verwendet. In 3D-Grafiken werden Oberflächennormalen, 3-Koordinatenvektoren der Länge 1 verwendet, um Beleuchtung und Reflexion auszudrücken. Es gab viele Oberflächennormale. Und um sie zu berechnen, müssen viele Vektoren normalisiert werden. Normalisierung ist oft nur ein schicker Begriff für Teilung. Der Satz des Pythagoras berechnet den Abstand zwischen Punkten, und das Teilen durch den Abstand hilft, Vektoren zu normalisieren:

Dieser Algorithmus ist am besten bekannt für seine Implementierung im Jahr 1999 im Quellcode des Quake III Arena-Spiels, eines Ego-Shooter-Videospiels, das 3D-Grafiken stark verwendete. Zu dieser Zeit war es im Allgemeinen rechenintensiv, den Kehrwert einer Gleitkommazahl zu berechnen, insbesondere in großem Maßstab; die schnelle inverse Quadratwurzel hat diesen Schritt umgangen.

Algorithmus:
Schritt 1: Die Bits der Gleitkommaeingabe werden als Ganzzahl neu interpretiert.

i = * ( long * ) &y;

Schritt 2: Es nimmt den resultierenden Wert und führt eine ganzzahlige Arithmetik durch, die eine Annäherung an den gesuchten Wert erzeugt.

i = 0x5f3759df - ( i >> 1 );

Schritt 3: Das Ergebnis ist jedoch nicht die Approximation selbst, sondern eine Ganzzahl, die zufällig, wenn Sie die Bits als Gleitkommazahl neu interpretieren, die Approximation ist. Der Code führt also die Umkehrung der Konvertierung in Schritt 1 durch, um zum Gleitkommawert zurückzukehren:

y = * ( float * ) &i;

Schritt 4: Und schließlich wird eine einzelne Iteration von Newtons Methode ausgeführt, um die Approximation zu verbessern.

y = y * ( threehalfs - ( x2 * y * y ) ); //threehalfs = 1.5F;

Der Algorithmus akzeptiert eine 32-Bit-Gleitkommazahl als Eingabe und speichert einen halbierten Wert zur späteren Verwendung. Dann werden die Bits, die die Gleitkommazahl darstellen, als 32-Bit-Ganzzahl behandelt, eine logische Verschiebung nach rechts um ein Bit durchgeführt und das Ergebnis von der magischen Zahl 0x5F3759DF subtrahiert. Dies ist die erste Näherung der inversen Quadratwurzel der Eingabe. Wenn die Bits erneut als Gleitkommazahl behandelt werden, wird eine Iteration der Newtonschen Approximationsmethode ausgeführt, wodurch eine genauere Approximation erzielt wird.

Angenommen, es gibt eine Zahl in Exponentenform oder wissenschaftlicher Notation:
${10^8}$ =100 million
Um nun die reguläre Quadratwurzel zu finden, teilen wir einfach den Exponenten durch 2:
${\ sqrt{{10^8}}}={10^{8/2}}={10^4}=10000$
Und wenn Sie die inverse Quadratwurzel kennen möchten, teilen Sie den Exponenten durch -2, um das Vorzeichen umzudrehen:
${\dfrac{1}{\sqrt{10^8}}}={10^{8/-2}}=10^{-4}=\ dfrac{1}{10000}$

Der Code konvertiert also die Gleitkommazahl in eine Ganzzahl. Es verschiebt dann die Bits um eins, was bedeutet, dass die Exponentenbits durch 2 geteilt werden (wenn wir die Bits schließlich wieder in einen Float umwandeln). Und schließlich, um den Exponenten zu negieren, subtrahieren wir von der magischen Zahl 0x5f3759df. Dies macht ein paar Dinge: Es bewahrt die Mantisse (der nicht exponentielle Teil, auch bekannt als 5 in: 5 · ), behandelt ungerade-gerade Exponenten, verschiebt Bits vom Exponenten in die Mantisse und alle möglichen funky Sachen.