John Carmack hat eine spezielle Funktion im Quake III-Quellcode, die die inverse Quadratwurzel eines Floats berechnet, 4x schneller als normal (float)(1.0/sqrt(x))
, einschließlich einer seltsamen 0x5f3759df
Konstante. Siehe den Code unten. Kann jemand Zeile für Zeile erklären, was genau hier vor sich geht und warum dies so viel schneller funktioniert als die reguläre Implementierung?
float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y;
i = 0x5f3759df - ( i >> 1 );
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) );
#ifndef Q3_VM
#ifdef __linux__
assert( !isnan(y) );
#endif
#endif
return y;
}
Antworten:
Zu Ihrer Information. Carmack hat es nicht geschrieben. Terje Mathisen und Gary Tarolli nehmen beide teilweise (und sehr bescheiden) Anerkennung dafür sowie einige andere Quellen.
Wie die mythische Konstante abgeleitet wurde, ist ein Rätsel.
Um Gary Tarolli zu zitieren:
Eine etwas bessere Konstante, die von einem erfahrenen Mathematiker (Chris Lomont) entwickelt wurde, um herauszufinden, wie der ursprüngliche Algorithmus funktioniert, ist:
Trotzdem erwies sich sein erster Versuch, eine mathematisch "überlegene" Version von ids sqrt (die fast dieselbe Konstante erreichte), als schlechter als die ursprünglich von Gary entwickelte, obwohl er mathematisch viel "reiner" war. Er konnte nicht erklären, warum es so gut war.
quelle
Natürlich stellt sich heutzutage heraus, dass es viel langsamer ist als nur die Verwendung des sqrt einer FPU (insbesondere unter 360 / PS3), da das Wechseln zwischen float- und int-Registern einen Load-Hit-Store induziert, während die Gleitkommaeinheit ein reziprokes Quadrat ausführen kann root in Hardware.
Es zeigt nur, wie sich Optimierungen entwickeln müssen, wenn sich die Art der zugrunde liegenden Hardware ändert.
quelle
Greg Hewgill und IllidanS4 gaben einen Link mit ausgezeichneter mathematischer Erklärung. Ich werde versuchen, es hier für diejenigen zusammenzufassen, die nicht zu sehr ins Detail gehen wollen.
Jede mathematische Funktion kann mit einigen Ausnahmen durch eine Polynomsumme dargestellt werden:
kann genau umgewandelt werden in:
Wobei a0, a1, a2, ... Konstanten sind . Das Problem ist, dass für viele Funktionen, wie die Quadratwurzel, diese Summe für den exakten Wert unendlich viele Mitglieder hat und nicht bei x ^ n endet . Aber wenn wir bei x ^ n anhalten haben wir immer noch ein Ergebnis mit einer gewissen Präzision.
Also, wenn wir haben:
In diesem speziellen Fall haben sie beschlossen, alle Polynomelemente über der Sekunde zu verwerfen, wahrscheinlich aufgrund der Berechnungsgeschwindigkeit:
Und jetzt ist die Aufgabe gekommen, a0 und a1 zu berechnen, damit y den geringsten Unterschied zum exakten Wert aufweist. Sie haben berechnet, dass die am besten geeigneten Werte sind:
Wenn Sie dies in eine Gleichung setzen, erhalten Sie:
Welches ist das gleiche wie die Zeile, die Sie im Code sehen:
Edit: eigentlich ist hier
y = 0x5f375a86 - 0.5*x
nicht das gleiche wiei = 0x5f375a86 - (i >> 1);
seit dem Verschieben von Float als Ganzzahl nicht nur durch zwei geteilt, sondern auch Exponent durch zwei geteilt und einige andere Artefakte verursacht, aber es kommt immer noch darauf an, einige Koeffizienten a0, a1, a2 ... zu berechnen.Zu diesem Zeitpunkt haben sie herausgefunden, dass die Genauigkeit dieses Ergebnisses für diesen Zweck nicht ausreicht. Daher haben sie zusätzlich nur einen Schritt der Newtonschen Iteration durchgeführt, um die Ergebnisgenauigkeit zu verbessern:
Sie hätten einige weitere Iterationen in einer Schleife durchführen können, wobei jede das Ergebnis verbessert, bis die erforderliche Genauigkeit erreicht ist. Genau so funktioniert es in CPU / FPU! Aber es scheint, dass nur eine Iteration ausreichte, was auch ein Segen für die Geschwindigkeit war. Die CPU / FPU führt so viele Iterationen wie nötig durch, um die Genauigkeit für die Gleitkommazahl zu erreichen, in der das Ergebnis gespeichert ist, und verfügt über einen allgemeineren Algorithmus, der in allen Fällen funktioniert.
Kurz gesagt, was sie getan haben, ist:
Verwenden Sie (fast) den gleichen Algorithmus wie CPU / FPU, nutzen Sie die Verbesserung der Anfangsbedingungen für den Sonderfall 1 / sqrt (x) und berechnen Sie nicht bis zur Präzision, zu der CPU / FPU gehen, sondern früher aufhören Berechnungsgeschwindigkeit gewinnen.
quelle
Nach diesem schönen Artikel vor einiger Zeit geschrieben ...
Es ist eine wirklich gute Lektüre. Dies ist nur ein winziges Stück davon.
quelle
Ich war neugierig zu sehen, was die Konstante als Float war, also schrieb ich einfach dieses Stück Code und googelte die Ganzzahl, die heraussprang.
Es sieht so aus, als ob die Konstante "Eine ganzzahlige Annäherung an die Quadratwurzel von 2 ^ 127 ist, besser bekannt durch die hexadezimale Form ihrer Gleitkommadarstellung 0x5f3759df" https://mrob.com/pub/math/numbers-18.html
Auf der gleichen Seite erklärt es das Ganze. https://mrob.com/pub/math/numbers-16.html#le009_16
quelle