Der Fast-Inverse-Square-Root-Algorithmus – Demo

Diese Seite baut auf der Seminararbeit von Paul Schulz mit dem Thema Der Fast-Inverse-Square-Root-Algorithmus mit Bezug zur 3D-Computergrafik aus 2023 auf. Sie dient zur Veranschaulichung der in der Seminararbeit theoretisch gewonnenen Erkenntnisse.

Der Algorithmus dient zur Approximation der folgenden Funktion:

$$f(x)=\frac{1}{\sqrt{x}}; \ D_f=F$$

Für eine positive normalisierte Fließkommazahl \(x \in F\) gilt nach IEEE 754:

$$x=(1+\frac{M}{2^{23}}) \cdot 2^{E-127}$$

Für die Interpretation einer solchen Fließkommazahl als natürliche Zahl \(z \in \mathbb{N}\) gilt:

$$z=E \cdot 2^{23}+M$$
8
3

Genaues Ergebnis

Zunächst wird das Ergebnis – im Rahmen der Genauigkeit einer Fließkommazahl – genau berechnet, um später das Ergebnis des Algorithmus vergleichen zu können. Annäherungen an \(f(x)\) werden stets zusammen mit dem relativen Fehler \(\delta\) in Prozent angegeben.

Erste Annäherung

Die nachfolgenden Tabellen zeigen jeweils die Komponenten einer Fließkommazahl, sowie die verschiedenen Interpretations-Möglichkeiten der Bitfolge.

Zunächst die eingegebene Zahl \(x\):

$$x$$
\(S\) \(E\) \(M\)
Binär
Dezimal
\(x\)
\(z\)

Anschließend wird die in der Seminararbeit beschriebene Zahl \(z_{y0}\) berechnet. Das Ergebnis wird in das Feld \(z\) der folgenden Tabelle eingetragen. Die Bitfolge dieser natürliche Zahl wird in die Komponenten Exponent und Mantisse zerlegt. Die daraus berechenbare rationale Zahl im Feld \(x\) stellt bereits die erste Annäherung \(y_0\) dar.

$$z_{y0}=c-\frac{1}{2} \cdot z_x$$
\(S\) \(E\) \(M\)
Binär
Dezimal
\(x\)
\(z\)

Newton-Verfahren

Im letzten Schritt wird noch die ausgewählte Anzahl an Newton-Iterationen durchgeführt. Die Iterationsvorschrift wird in der Seminararbeit hergeleitet.

$$y_{n+1}=\frac{1}{2} \cdot y_n \cdot (3-x \cdot y_n^2)$$