Alles über den Fast-Inverse-Square-Root-Algorithmus

Alles über den Fast-Inverse-Square-Root-Algorithmus

Algorithmus

• Der Fast-Inverse-Square-Root-Algorithmus ist ein Algorithmus, der durch den Quake-3-Quellcode berühmt wurde und von John Carmack verwendet wurde.
• Dieser Algorithmus manipuliert die Bits von Gleitkommazahlen, um die inverse Quadratwurzel schnell zu berechnen.
• Codebeispiel:

  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 ) );  // 1차 반복
  
    return y;
  }
  

32-Bit-Gleitkommazahl: Darstellung

• IEEE-754-32-Bit-Gleitkommazahlen bestehen aus drei Komponenten:
  • Vorzeichen: 1 Bit, zeigt an, ob die Zahl positiv oder negativ ist.
  • Exponent: 8 Bit, bestimmt den Wertebereich der Zahl.
  • Mantisse: 23 Bit, legt die Position der Zahl innerhalb dieses Bereichs fest.
• Der tatsächliche Wert wird wie folgt berechnet:

  N = -1^S * 2^(E-127) * (1 + M/2^23)
  

32-Bit-Gleitkommazahl: Bit-Interpretation

• Die interne Darstellung von Gleitkommazahlen ist für Programmierer normalerweise nicht wichtig.
• Wenn man diese Darstellung jedoch gut versteht, lassen sich effiziente Algorithmen entwerfen.
• Interpretiert man das Bitmuster einer Gleitkommazahl als Ganzzahl, ergibt sich eine Näherung der Logarithmusfunktion.

  log2(x) ≈ Ix / L - B
  

Newton-Verfahren

• Zur Verbesserung des Anfangsnäherungswerts wird das Newton-Verfahren (Newton's method) verwendet.
• Das Newton-Verfahren ist ein Algorithmus, der Näherungswerte für eine gegebene Funktion iterativ verbessert.
• Codebeispiel:

  y = y * ( threehalfs - ( x2 * y * y ) ); // 1차 반복
  

Fazit

• Dieser Algorithmus wurde auf Basis eines tiefen Verständnisses der internen mathematischen Details des Gleitkommasystems entworfen und nutzt Operationen, die auf Computern schnell ausgeführt werden können.
• Der genaue Ursprung des Algorithmus ist unklar, aber er ist ein Beispiel für äußerst effizientes und gut durchdachtes Engineering.

Meinung von GN⁺

• Historische Bedeutung: Dieser Algorithmus war ein innovativer Ansatz, um die Hardware-Beschränkungen der damaligen Zeit zu überwinden.
• Didaktischer Wert: Er hilft sehr dabei, die interne Struktur von Gleitkommazahlen und die zugrunde liegenden mathematischen Prinzipien zu verstehen.
• Moderne Anwendung: Auf moderner Hardware ist er möglicherweise weniger nötig, aber die Prinzipien des Algorithmus sind weiterhin nützlich.
• Optimierungspotenzial: Der Konstantenwert des Algorithmus kann optimiert werden, was Raum für weitere Forschung lässt.
• Kritische Perspektive: Da es auf moderner Hardware bessere Methoden geben kann, ist es wichtig, ihn stets mit aktuellen Technologien zu vergleichen.

[joyfui]

Dieser faszinierende Code taucht immer wieder auf, sobald man ihn fast vergessen hat.. haha

[GN⁺]

Hacker-News-Kommentare

• Unterstützung für SSE-Befehle: Computer, die nach 1999 hergestellt wurden, unterstützen den SSE-Befehlssatz, und mit dem Befehl _mm_rsqrt_ps lässt sich die inverse Quadratwurzel schnell berechnen.

• Fortschritte moderner Hardware: Auf moderner Hardware kann die Berechnung der inversen Quadratwurzel auf der CPU schnell erfolgen, und es ist ein Irrtum, alle Gleitkommaoperationen auf die GPU auszulagern.

• MMIX-Implementierung: Es gibt Beispielcode, der die Berechnung der inversen Quadratwurzel in MMIX implementiert. Dieser Code geht ursprünglich davon aus, dass die Zahl größer als 2^-1021 ist.

• Tippfehler in der Formel: In der Gleitkommaformel gibt es einen Tippfehler. Sie sollte zu (-1)^S korrigiert werden.

• Interpretation des Logarithmus: Die Interpretation des rohen Bitmusters ist keine stückweise lineare Approximation des Logarithmus. Die Linien zwischen den Datenpunkten existieren in Wirklichkeit nicht.

• Wikipedia als Referenz: Es gibt auf Wikipedia eine gute Diskussion über diese Funktion und ihre Geschichte. Wikipedia-Link

• GitHub-Code-Sammlung: Einige dazugehörige Codes wurden auf GitHub gesammelt. GitHub-Link

• StackOverflow als Referenz: Sehenswert ist auch eine StackOverflow-Frage zu optimierten Approximationen niedriger Genauigkeit. StackOverflow-Link

• Erfahrung mit der Optimierung von 3D-Engines: Schon vor Quake wurde beim Bau von 3D-Engines Optimierungserfahrung gesammelt, und algorithmische Optimierung gewinnt immer.

• YouTube-Video-Empfehlung: Es gibt ein interessantes Video zu diesem Thema. YouTube-Link

• Produktivitäts-Zeitdieb: Sich in dieses Thema zu vertiefen, hat viel produktive Zeit gekostet.

• Optimale magische Zahl: Die magische Zahl im berühmten Code-Snippet ist nicht die optimale Konstante. Es ist möglich, eine bessere Konstante zu finden, und mit einem Jupyter-Notebook kann man die optimale magische Zahl ermitteln.