Understanding Quake’s Fast Inverse Square Root

Ein Artikel und eine Forschungsarbeit beschreiben eine schnelle, scheinbar magische Methode zur Berechnung der inversen Quadratwurzel ($ 1 / \ sqrt{x} $), die im Spiel Quake verwendet wird.

Ich bin kein Grafikexperte, weiß aber zu schätzen, warum Quadratwurzeln nützlich sind. Der Satz des Pythagoras berechnet die Entfernung zwischen Punkten, und die Division durch die Entfernung hilft, Vektoren zu normalisieren. (Normalisierung ist oft nur ein schicker Begriff für Division.)

3D-Spiele wie Quake teilen sich durch die Entfernung Zillionen (ja Zillionen) Mal pro Sekunde, so dass „kleinere“ Leistungsverbesserungen immens helfen. Wir wollen nicht die Quadratwurzel nehmen und den regulären Weg teilen: Potenzierung und Division sind wirklich, wirklich teuer für die CPU.

Unter diesen Bedingungen ist hier die Zauberformel, um $ 1 / \ sqrt{x} $ zu erhalten, wie in Quake gefunden (meine Kommentare eingefügt):

Mein Verständnis: Dieser unglaubliche Hack schätzt die inverse Wurzel mit Newtons Näherungsmethode und beginnt mit einer großartigen ersten Vermutung.

Um die Vermutung anzustellen, wird eine Gleitkommazahl in wissenschaftlicher Notation verwendet und & mit dem Exponenten negiert, um etwas in der Nähe der inversen Quadratwurzel zu erhalten. Es läuft dann eine Runde von Newtons Approximationsmethode, um die Schätzung weiter zu verfeinern und tada, wir haben etwas in der Nähe der inversen Quadratwurzel.

Newtons Näherungsmethode

Newtons Methode kann verwendet werden, um ungefähre Wurzeln jeder Funktion zu finden. Sie können die Methode weiter iterieren, um immer näher an die Wurzel heranzukommen, aber diese Funktion verwendet nur 1 Schritt! Hier ist ein Crash-Kurs über Newtons Methode (es war neu für mich):

Sie können diesen Vorgang wiederholen (indem Sie Ihre neue Vermutung in die Formel einfügen) und nähere Näherungen für Ihre Wurzel erhalten. Schließlich haben Sie eine „neue Vermutung“, die f (neue Vermutung) wirklich, wirklich nahe an Null macht – es ist eine Wurzel! (Oder nahe genug für Regierungsarbeit, wie sie sagen).

Natürlich wollen wir unseren Fehler so klein wie möglich machen. Das bedeutet, das „x“ zu finden, das Fehler (x) = 0 macht, was dasselbe ist wie das Finden der Wurzel der Fehlergleichung. Wenn wir Fehler (x) in die Newtonsche Näherungsformel einfügen:

und nehmen Sie die richtigen Derivate:

wir können sie anschließen, um die Formel für eine bessere Vermutung zu erhalten:

Welches ist genau die Gleichung, die Sie im obigen Code sehen, und denken Sie daran, dass x unsere neue Vermutung (g) ist und „xhalf“ die Hälfte des ursprünglichen Wertes ist ($ 0.5 i$):

x = x*(1.5f - xhalf*x*x);

Mit dieser Formel können wir mit einer Vermutung „g“ beginnen und die Formel wiederholen, um bessere Vermutungen zu erhalten. Probieren Sie diese Demo aus, um mehrere Iterationen zu verwenden, um das inverse Quadrat zu finden:

Meine Freunde, die Frage lautet also: „Wie können wir eine gute erste Vermutung anstellen?“

Eine gute Vermutung machen

Was ist eine gute Vermutung für die inverse Quadratwurzel? Es ist ein bisschen eine Trickfrage – unsere beste Vermutung für die inverse Quadratwurzel ist die inverse Quadratwurzel selbst!

Ok hotshot, du fragst, wie bekommen wir eigentlich $1/\sqrt{x}$ ?

Hier setzt die Magie an. Angenommen, Sie haben eine Zahl in Exponentenform oder wissenschaftlicher Notation:

Wenn Sie nun die reguläre Quadratwurzel finden möchten, teilen Sie einfach den Exponenten durch 2:

Und wenn Sie die inverse Quadratwurzel möchten, teilen Sie den Exponenten durch -2, um das Vorzeichen umzudrehen:

Wie können wir also den Exponenten einer Zahl ohne andere teure Operationen erhalten?

Floats werden in Mantissen-Exponentenform gespeichert

Nun, wir haben Glück. Gleitkommazahlen werden von Computern in Mantissen-Exponenten-Form gespeichert, so dass es möglich ist, den Exponenten zu extrahieren und zu teilen!

Aber anstatt explizit eine Division durchzuführen (teuer für die CPU), verwendet der Code einen anderen cleveren Hack: Er verschiebt Bits. Das Verschieben nach rechts um eine Position ist dasselbe wie das Teilen durch zwei (Sie können dies für jede Potenz von 2 versuchen, aber der Rest wird abgeschnitten). Und wenn Sie eine negative Zahl erhalten möchten, anstatt mit -1 zu multiplizieren (Multiplikationen sind teuer), subtrahieren Sie einfach die Zahl von „0“ (Subtraktionen sind billig).

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-Exponenten-Teil, auch bekannt als 5 in: $ 5 \ cdot 10 ^ 6 $), behandelt ungerade-gerade Exponenten, verschiebt Bits vom Exponenten in die Mantisse und alle möglichen funky Sachen. Das Papier hat mehr Details und Erklärungen, ich habe nicht alles beim ersten Mal verstanden. Wie immer können Sie gerne kommentieren, wenn Sie eine bessere Erklärung dafür haben, was passiert.

Das Ergebnis ist, dass wir eine erste Vermutung erhalten, die der realen inversen Quadratwurzel sehr nahe kommt! Wir können dann eine einzelne Runde von Newtons Methode machen, um die Vermutung zu verfeinern. Mehr Runden sind möglich (mit zusätzlichem Rechenaufwand), aber eine Runde ist alles, was für die benötigte Präzision benötigt wird.

Also, warum die magische Zahl?

Der große Hack ist, wie ganze Zahlen und Gleitkommazahlen gespeichert werden. Gleitkommazahlen wie $ 5.4 \ cdot 10 ^ 6 $ speichern ihren Exponenten in einem separaten Bitbereich als „5.4“. Wenn Sie die gesamte Zahl verschieben, teilen Sie den Exponenten durch 2 sowie die Zahl (5.4) durch 2. Hier kommt die magische Zahl ins Spiel – sie macht einige coole Korrekturen für diese Division, die ich nicht ganz verstehe. Es gibt jedoch mehrere magische Zahlen, die verwendet werden könnten – diese minimiert den Fehler in der Mantisse.

Die magische Zahl korrigiert auch gerade / ungerade Exponenten; Das Papier erwähnt, dass Sie auch andere magische Zahlen finden können.

Ressourcen

Es gibt weitere Diskussionen auf reddit (Benutzer pb_zeppelin) und slashdot:

• http://games.slashdot.org/article.pl?sid=06/12/01/184205 und mein Kommentar

Andere Beiträge in dieser Serie

1. Zahlensysteme und Basen
2. Die Kurzanleitung zu GUIDs
3. Die schnelle inverse Quadratwurzel von Quake verstehen
4. Eine einfache Einführung in Computernetzwerke
5. Tauschen Sie zwei Variablen mit XOR aus
6. Little-Endian-Byte-Reihenfolge
7. Unicode und Sie
8. Ein wenig Diddy über binäre Dateiformate
9. Sortieralgorithmen