gyors inverz négyzetgyök egy algoritmus, amely becsüli , 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:
=100 millió
most, hogy megtaláljuk a szabályos négyzetgyököt, csak elosztjuk a kitevőt 2:
Ha pedig meg akarja tudni az inverz négyzetgyököt, ossza el a kitevőt -2-vel a jel megfordításához:
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 · ), 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: