Understanding Quake’ s Fast Inverse Square Root
egy cikk és kutatási cikk leírja a Quake játékban használt inverz négyzetgyök ($1/\sqrt{x}$) kiszámításának gyors, látszólag varázslatos módját.
nem vagyok grafikus szakértő, de értékelem, hogy miért négyzetgyök hasznosak. A Pitagorasz-tétel kiszámítja a pontok közötti távolságot, és a távolsággal való elosztás segít normalizálni a vektorokat. (A normalizáció gyakran csak egy divatos kifejezés a megosztásra.)
3D-s játékok, mint a Quake divide távolság zillions (igen zillions) alkalommal másodpercenként, így a “kisebb” teljesítmény fejlesztések segítségével mérhetetlenül. Nem akarjuk a négyzetgyököt és a szokásos módon osztani: a hatványozás és az Osztás nagyon-nagyon drága a CPU számára.
tekintettel ezekre a feltételekre, itt van a mágikus képlet, hogy $1/\sqrt{x}$, amint azt a Quake (megjegyzéseim beillesztve):
megértésem: ez a hihetetlen hack becsüli az inverz gyökeret Newton közelítési módszerével, és nagyszerű kezdeti találgatással kezdődik.
ahhoz, hogy a találgatás, úgy lebegőpontos szám tudományos jelöléssel, és tagadja & felét a kitevő, hogy valami közel az inverz négyzetgyök. Ezután lefuttat egy kört Newton közelítési módszerével, hogy tovább finomítsa a becslést, és tada, van valami az inverz négyzetgyök közelében.
Newton közelítési módszere
Newton módszerével bármilyen függvény hozzávetőleges gyökereit meg lehet találni. Folytathatja a módszer iterálását, hogy egyre közelebb kerüljön a gyökérhez, de ez a funkció csak 1 lépést használ! Itt van egy összeomlási tanfolyam Newton módszeréről (számomra új volt):
megismételheti ezt a folyamatot (bedugva az új találgatást a képletbe), és közelebb kerülhet a gyökérhez. Végül van egy” új találgatás”, ami f(új találgatás) nagyon, nagyon közel nulla-ez egy gyökér! (Vagy elég közel a kormányzati munkához, ahogy mondják).
nyilvánvaló, hogy a lehető legkisebbre akarjuk tenni a hibánkat. Ez azt jelenti, hogy megtaláljuk az” x ” hibát(x) = 0, ami megegyezik a hibaegyenlet gyökerének megtalálásával. Ha az(x) hibát bedugjuk Newton közelítési képletébe:
vegyük a megfelelő derivatívákat:
mi lehet csatlakoztatni őket, hogy a képlet egy jobb kitalálni:
pontosan ezt az egyenletet látja a fenti kódban, emlékezve arra, hogy x az új találgatásunk (g), az “xhalf” pedig az eredeti érték fele (0,5 USD i$):
x = x*(1.5f - xhalf*x*x);
ezzel a képlettel kezdhetjük a “g” találgatással, és megismételhetjük a képletet, hogy jobb találgatásokat kapjunk. Próbálja ki ezt a bemutatót több iteráció használatához az inverz négyzet megtalálásához:
tehát barátaim, a kérdés: “hogyan tudunk jó kezdeti találgatást készíteni?”
jó találgatás
mi a jó találgatás az inverz négyzetgyökre? Ez egy kicsit beugratós kérdés – a legjobb tippünk az inverz négyzetgyökre maga az inverz négyzetgyök!
Ok hotshot, kérdezed, hogyan kapunk valójában $1/ \ sqrt{x}$ – t?
itt kezdődik a varázslat. Tegyük fel, hogy van egy szám exponens formában vagy tudományos jelöléssel:
most, ha meg akarja találni a szabályos négyzetgyököt, akkor csak elosztja a kitevőt 2:
Ha pedig az inverz négyzetgyököt szeretné, ossza el a kitevőt -2-vel a jel megfordításához:
Szóval, hogyan kaphatjuk meg a szám kitevőjét más drága műveletek nélkül?
az úszókat mantissa-kitevő formában tárolják
nos, szerencsénk van. A lebegőpontos számokat a számítógépek mantissa-kitevő formában tárolják, így lehetséges a kitevő kivonása és felosztása!
de ahelyett, hogy kifejezetten osztást végezne (drága a CPU számára), a kód egy másik okos feltörést használ: biteket vált. A jobb oldali eltolás egy pozícióval megegyezik a kettővel való osztással (ezt kipróbálhatja bármely 2-es hatványnál, de a maradékot megcsonkítja). Ha pedig negatív számot szeretne kapni, ahelyett, hogy -1-gyel szorozna (a szorzások drágák), csak vonja le a számot a “0” – ból (a kivonások olcsóak).
tehát a kód a lebegőpontos számot egész számmá 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 a kitevő tagadásához kivonjuk a 0x5f3759df bűvös számból. Ez néhány dolgot tesz: megőrzi a mantissát (a nem exponens rész, más néven 5 in: $5 \cdot 10^6$), kezeli a páratlan-páros kitevőket, a biteket az exponensről a mantissára mozgatja, és mindenféle funky dolgot. Az újságnak több részlete és magyarázata van, először nem értettem meg mindent. Mint mindig, nyugodtan kommentáljon, ha jobb magyarázata van a történésekre.
az eredmény az, hogy kapunk egy kezdeti találgatás, hogy valóban közel van a valós inverz négyzetgyök! Ezután megtehetjük a Newton módszerének egyetlen fordulóját, hogy finomítsuk a találgatást. Több forduló lehetséges (további számítási költséggel), de egy kör minden, ami szükséges a szükséges pontossághoz.
szóval, miért a mágikus szám?
a nagy hack, hogyan egész számok és lebegőpontos számok vannak tárolva. Lebegőpontos számok, mint 5 dollár.4 \ cdot 10^6$ kitevőjüket külön bittartományban tárolják, mint az “5.4”. A teljes szám eltolásakor a kitevőt 2-vel osztja el, valamint a számot (5.4) 2-vel is elosztja. Itt jön képbe a bűvös szám — csinál néhány klassz korrekciót ehhez a részleghez, amit nem egészen értek. Azonban számos mágikus szám használható – ez történik, hogy minimalizálja a mantissa hibáját.
a bűvös szám korrigálja a Páros / páratlan kitevőket is; a cikk megemlíti, hogy más mágikus számokat is találhat.
források
további vita folyik a Redditről (pb_zeppelin felhasználó) és a slashdot-ról:
- http://games.slashdot.org/article.pl?sid=06/12/01/184205 és az én megjegyzésem
Egyéb Hozzászólások ebben a sorozatban
- számrendszerek és bázisok
- a Gyors útmutató GUIDs
- megértése Quake gyors inverz négyzetgyök
- Egy egyszerű bevezetés a számítógépes hálózati
- Swap két változó segítségével XOR
- megértése nagy és little endian byte order
- Unicode és te
- egy kis Diddy a bináris fájlformátumokról
- rendezési algoritmusok