GeeksforGeeks

gyors inverz négyzetgyök egy algoritmus, amely becsüli  {\dfrac{1}{\sqrt{x}}}, a reciprok (vagy multiplikatív inverz) a négyzetgyök egy 32 bites lebegőpontos szám x IEEE 754 lebegőpontos formátumban. A kölcsönös négyzetgyökek kiszámítása számos alkalmazásban szükséges, mint például a vektor normalizálása a videojátékokban, és leginkább a 3D programozás számításaiban használják. A 3D-s grafika, felületi normálok, 3-koordináta Vektorok hossza 1 használják, hogy kifejezze a világítás és a visszaverődés. Sok felszíni normális volt. Ezek kiszámítása sok vektor normalizálásával jár. A normalizálás gyakran csak egy divatos kifejezés a megosztásra. A Pitagorasz-tétel kiszámítja a pontok közötti távolságot, a távolsággal való elosztás pedig segít normalizálni a vektorokat:

ez az algoritmus leginkább arról ismert, hogy 1999-ben végrehajtotta a Quake III aréna játék, egy első személyű lövöldözős videojáték, amely erősen felhasználta a 3D grafikát. Abban az időben számítási szempontból általában drága volt a lebegőpontos szám reciprokának kiszámítása, különösen nagy léptékben; a gyors inverz négyzetgyök megkerülte ezt a lépést.

algoritmus:
1.lépés : a lebegőpontos bemenet bitjeit egész számként értelmezi újra.

i = * ( long * ) &y; 

2.lépés : az eredményül kapott értéket egész számtani módon végzi, amely a keresett érték közelítését eredményezi.

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

3.lépés : az eredmény nem maga a közelítés, hanem egy egész szám, amely történetesen, ha újraértelmezi a biteket lebegőpontos számként, a közelítés. Tehát a kód az 1. lépésben a konverzió fordítottját hajtja végre, hogy visszatérjen a lebegőponthoz:

y = * ( float * ) &i;

4. lépés: végül a Newton-módszer egyetlen iterációját futtatja a közelítés javítása érdekében.

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

az algoritmus egy 32 bites lebegőpontos számot fogad el bemenetként, és egy felezett értéket tárol későbbi használatra. Ezután a lebegőpontos számot képviselő biteket 32 bites egész számként kezelve egy logikai eltolást hajtunk végre egy bittel jobbra, és az eredményt levonjuk a 0x5f3759df bűvös számból. Ez a bemenet inverz négyzetgyökének első közelítése. A biteket ismét lebegőpontos számként kezelve Newton közelítési módszerének egy iterációját futtatja, pontosabb közelítést eredményezve.

tegyük fel, hogy van egy szám kitevő formában vagy tudományos jelölésben:
{10^8} =100 millió
most, hogy megtaláljuk a szabályos négyzetgyököt, csak elosztjuk a kitevőt 2:
{\sqrt{{10^8}}}={10^{8/2}}={10^4}=10000
Ha pedig meg akarja tudni az inverz négyzetgyököt, ossza el a kitevőt -2-vel a jel megfordításához:
 {\dfrac{1} {\sqrt{10^8}}}={10^{8/-2}}=10^{-4}=\dfrac{1}{10000}

tehát a kód a lebegőpontos számot egész számgá alakítja. Ezután eggyel eltolja a biteket, ami azt jelenti, hogy az exponens biteket elosztjuk 2-vel (amikor végül a biteket lebegővé változtatjuk). Végül pedig az exponens tagadásához kivonjuk a 0x5f3759df bűvös számból. Ez néhány dolgot tesz: megőrzi a mantisszát (a nem exponens rész, más néven 5 ban ben: 5 · 10^8), páratlan-páros kitevőket kezel, biteket vált a kitevőből a mantisszába, és mindenféle funky dolgot.

a következő kód a Quake III Arena gyors inverz négyzetgyök megvalósítása (pontos eredeti megjegyzés a Quake III Arena játékban).

#include<bits/stdc++.h>
using namespace std;
float inverse_rsqrt( float number )
{
const float threehalfs = 1.5F;
float x2 = number * 0.5F;
float y = number;
long i = * ( long * ) &y;
i = 0x5f3759df - ( i >> 1 );
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) );
return y;
}
int main(){
int n = 256;
float f = inverse_rsqrt(n);
cout << f << endl;
return 0;
}



kimenet:



+