desno|mini|Izračuni osvjetljenja i refleksije, kao u videoigri OpenArena, koriste brzi inverzni kod kvadratnog korijena za izračunavanje kutova upada i refleksije. Brzi inverzni kvadratni korijen ili heksadecimalna konstanta je algoritam koji procjenjuje , recipročna vrijednost (ili multiplikativni inverz) kvadratnog korijena 32-bitnog broja s pomičnim zarezom u IEEE 754 formatu s pomičnim zarezom. Algoritam je najpoznatiji po svojoj primjeni u videoigri Quake III Arena, pucačine iz prvog lica izdanoj 1999. koja se uvelike temelji na 3D grafici. S kasnijim napretkom hardwarea, posebno naredbom x86 SSE rsqrtss, ovaj algoritam općenito nije najbolji izbor za moderna računala, iako ostaje zanimljiv povijesni primjer.

Algoritam prihvaća 32-bitni broj s pomičnim zarezom kao ulaz i pohranjuje prepolovljenu vrijednost za kasniju upotrebu. Zatim, tretirajući bitove koji predstavljaju broj s pomičnim zarezom kao 32-bitni cijeli broj, izvodi se logički pomak udesno za jedan bit i rezultat se oduzima od broja, što je prikaz aproksimacije u obliku pomične točke . To rezultira prvom aproksimacijom inverznog kvadratnog korijena ulaza. Ponovno tretirajući bitove kao broj s pomičnim zarezom, pokreće se jedna iteracija Newtonove metode, što daje precizniju aproksimaciju.

Povijest William Kahan i KC Ng u Berkeleyu napisali su neobjavljeni rad u svibnju 1986. u kojem opisuju kako izračunati kvadratni korijen koristeći tehnike mijenjanja bitova nakon čega slijede Newtonove iteracije. Krajem 1980-ih, Cleve Moler u Ardent Computeru saznao je za ovu tehniku i prenio je svom kolegi Gregu Walshu. Greg Walsh osmislio je sada poznati konstantni i brzi inverzni algoritam kvadratnog korijena. Gary Tarolli bio je savjetnik za Kubotu, tvrtki koja je u to vrijeme financirala Ardent, i vjerojatno je donio algoritam u 3dfx Interactive oko 1994.

Jim Blinn demonstrirao je jednostavnu aproksimaciju inverznog kvadratnog korijena u kolumni iz 1997. za IEEE Computer Graphics and Applications. Povratnim inženjerstvom drugih suvremenih 3D videoigara otkrivena je inačica algoritma u Activisionovoj igri Interstate '76 iz 1997.

Quake III Arena, pucačine iz prvog lica, koju je 1999. izdao Id Software koristila se algoritmom. Brian Hook možda je prenio algoritam iz 3dfx-a u id Software. Rasprava o kôdu pojavila se na kineskom forumu za razvojne programere CSDN 2000. godine, a Usenet i forum »gamedev.net« široko su proširili kôd 2002. i 2003. godine. Pojavile su se nagađanja o tome tko je napisao algoritam i kako je ta konstanta izvedena; neki su pretpostavljali da je to John Carmack. Puni izvorni kôd Quake III je na QuakeConu 2005., ali nije dao odgovore. Pitanje autorstva riješeno je 2006. godine kada je Greg Walsh, izvorni autor, kontaktirao Beyond3D nakon što su njihova nagađanja stekla popularnost na Slashdotu .

Godine 2007. algoritam je primijenjen u neke namjenske hardverske vertex shadere korištenjem programirljivih logičkih nizova (FPGA).

Motivacija desno|mini|Površinske normale opsežno se koriste u izračunima osvjetljenja i sjenčanja, što zahtijeva izračun normi za vektore. Ovdje je prikazano polje vektora normalnih na površinu. desno|mini|Dvodimenzionalni primjer korištenja normale za izračun kuta refleksije iz kuta upada; u ovom slučaju, na svjetlost koja se odbija od zakrivljenog zrcala. Brzi inverzni kvadratni korijen koristi se za generalizaciju ovog izračuna na trodimenzionalni prostor. Inverzni kvadratni korijen broja s pomičnim zarezom koristi se u digitalnoj obradi signala za normalizaciju vektora, skalirajući ga na duljinu 1 kako bi se dobio jedinični vektor. Na primjer, programi računalne grafike koriste inverzne kvadratne korijene za izračunavanje kutova upada i refleksije za osvjetljenje i sjenčanje. 3D grafički programi moraju izvršiti milijune ovih izračuna svake sekunde kako bi simulirali osvjetljenje. Kada je kod razvijen početkom 1990-ih, većina procesorske snage za pomični zarez zaostajala je za brzinom obrade cijelih brojeva. To je bilo problematično za 3D grafičke programe prije pojave specijaliziranog hardvera za rukovanje transformacijom i osvjetljenjem. Izračunavanje kvadratnih korijena obično ovisi o mnogim operacijama dijeljenja, koje su za brojeve s pomičnim zarezom računalno skupe. Brzi inverzni kvadrat generira dobru aproksimaciju sa samo jednim korakom dijeljenja.

Duljina vektora određuje se izračunavanjem njegove euklidske norme: kvadratnog korijena zbroja kvadrata komponenti vektora. Kada se svaka komponenta vektora podijeli s tom duljinom, novi vektor bit će jedinični vektor usmjeren u istom smjeru. U 3D grafičkom programu svi vektori nalaze se u trodimenzionalnom prostoru, pa bio bi vektor Zatim,

je euklidska norma vektora, a normalizirani (jedinični) vektor je

gdje je razlomljeni član inverzni kvadratni korijen od .

U to vrijeme, dijeljenje s pomičnim zarezom bilo je općenito skupo u usporedbi s množenjem; brzi algoritam inverznog kvadratnog korijena zaobilazio je korak dijeljenja, dajući mu prednost.

Pregled koda Sljedeći kod u jeziku C brza je implementacija inverznog kvadratnog korijena iz Quake III Arene, bez C direktiva predprocesora, ali uključujući točan izvorni tekst komentara: float Q_rsqrt( float number ) { long i; float x2, y; const float threehalfs = 1.5F;

x2 = number * 0.5F; y = number; i = * ( long * ) &y; // evil floating point bit level hacking i = 0x5f3759df - ( i >> 1 ); // what the fuck? y = * ( float * ) &i; y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration // y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed

return y; }U to vrijeme, opća metoda za izračunavanje inverznog kvadratnog korijena bila je izračunavanje aproksimacije za , a zatim revizija te aproksimacije drugom metodom dok nije došla unutar prihvatljivog raspona pogreške stvarnog rezultata. Uobičajene softverske metode početkom 1990-ih crpile su aproksimacije iz tablice pretraživanja. Ključ brzog inverznog kvadratnog korijena bio je izravan izračun aproksimacije korištenjem strukture brojeva s pomičnim zarezom, što se pokazalo bržim od pretraživanja tablice. Algoritam je bio otprilike četiri puta brži od izračuna kvadratnog korijena drugom metodom i izračuna recipročne vrijednosti putem dijeljenja s pomičnim zarezom. Algoritam je dizajniran imajući na umu specifikaciju IEEE 754-1985 za 32-bitni pomični zarez, ali istraživanje Chrisa Lomonta pokazalo je da se može primijeniti i u drugim specifikacijama brojeva s pomičnim zarezom.

Prednosti u brzini koje je nudio trik s brzim inverznim kvadratnim korijenom proizašle su iz tretiranja 32-bitne riječi s pomičnim zarezomUse of the type long reduces the portability of this code on modern systems. For the code to execute properly, sizeof(long) must be 4 bytes, otherwise negative outputs may result. Under many modern 64-bit systems, sizeof(long) is 8 bytes. The more portable replacement is int32_t. kao cijelog broja, a zatim njenog oduzimanja od „čarobne konstante”.{ Ovo oduzimanje cijelih brojeva i pomicanje bitova rezultira uzorkom bitova koji je, kada se redefinira kao broj s pomičnim zarezom, gruba aproksimacija inverznog kvadratnog korijena broja. Izvodi se jedna iteracija Newtonove metode kako bi se postigla određena točnost i kod je završen. Algoritam generira razumno točne rezultate koristeći jedinstvenu prvu aproksimaciju za Newtonovu metodu; međutim, mnogo je sporiji i manje točan od korištenja SSE instrukcije rsqrtss na x86 procesorima također objavljenim 1999.

Obrađeni primjer Kao primjer, broj može se koristiti za izračunavanje Prvi koraci algoritma ilustrirani su u nastavku: 0011_1110_0010_0000_0000_0000_0000_0000_0000 Bitni uzorak za x i i 0001_1111_0001_0000_0000_0000_0000_0000 Pomakni desno za jednu poziciju: (i > > 1) 0101_1111_0011_0111_0101_1001_1101_1111 Čarobni broj 0x5F3759DF 0100_0000_0010_0111_0101_1001_1101_1111 Rezultat 0x5F3759DF - (i > > 1) Interpretacija kao IEEE 32-bitna reprezentacija: 0_01111100_01000000000000000000000 1,25 × 2 −3 0_00111110_00100000000000000000000 1,125 × 2 −65 0_10111110_01101110101100111011111 1,432430... × 2 63 0_10000000_01001110101100111011111 1,307430... × 2 1 Reinterpretacijom ovog posljednjeg uzorka bitova kao broja s pomičnim zarezom dobiva se aproksimacija , što ima pogrešku od oko 3,4%. Nakon jedne iteracije Newtonove metode, konačni rezultat je , pogreška od samo 0,17%.

Izbjegavanje nedefinirana ponašanja Prema C standardu, reinterpretacija vrijednosti s pomičnim zarezom kao cijelog broja pretvaranjem, a zatim dereferenciranjem pokazivača na njega može uzrokovati nedefinirano ponašanje u slučaju da se veličine cijelog broja i b s projaomičnim zarezom ne podudaraju na danoj arhitekturi. To se može izbjeći korištenjem alternativnih tehnika igranja riječima tipova kao što su C-ove unije ili C++20 -ov std::bit_cast .

Algoritam Algoritam izračunava izvođenjem sljedećih koraka:

Alias argument cijeli broj kao način izračuna aproksimacije binarnog logaritma Upotrijebite ovu aproksimaciju za izračunavanje aproksimacije Alias natrag u float, kao način izračunavanja aproksimacije eksponencijalne funkcije baze 2 Poboljšajte aproksimaciju korištenjem jedne iteracije Newtonove metode.

Reprezentacija s pomičnim zarezom Budući da se ovaj algoritam uvelike oslanja na bitnu reprezentaciju brojeva s pomičnim zarezom jednostruke preciznosti, ovdje je dan kratki pregled te reprezentacije. Za kodiranje realnog broja različitog od nule kao jednostruki precizni float, prvi korak je napisati kao normalizirani binarni broj:

gdje je eksponent je cijeli broj, i je binarni prikaz značajnosti . Budući da je jedini bit prije točke u značajnosti uvijek 1, ne treba ga pohranjivati. Jednadžba se može prepisati kao:

gdje sredstva , pa Iz ovog oblika izračunavaju se tri neoznačena cijela broja:

, the "sign bit", is if is positive and negative or zero (1 bit) is the "biased exponent", where is the "exponent bias" should be in the range for to be representable as a normal number. (8 bits) , where The only real numbers that can be represented exactly as floating point are those for which is an integer. Other numbers can only be represented approximately by rounding them to the nearest exactly representable number. (23 bits)

Dakle: i .

Ta se polja zatim pakiraju, s lijeva na desno, u 32-bitni spremnik.

Kao primjer, ponovno razmotrimo broj Normaliziranje prinosi:

i stoga su tri nepotpisana cjelobrojna polja:

Ova polja su pakirana kao što je prikazano na slici ispod: središte Broj se binarno predstavlja kao:

Također, budući da ovaj algoritam radi na realnim brojevima, definiran je samo za Kod stoga pretpostavlja i .

Broj, dan za izračun kvadratnog korijena, mogao bi se prepisati kao:

Aliasiranje na cijeli broj kao približni logaritam Ako bi se izračunali bez računala ili kalkulatora, tablica logaritama bila bi korisna, zajedno s identitetom , što vrijedi za svaku bazu Brzi inverzni kvadratni korijen temelji se na ovom identitetu i na činjenici da aliasiranje float32 cijelom broju daje grubu aproksimaciju njegovog logaritma. Evo kako:

Ako je pozitivan normalan broj :

zatim

i otkad , logaritam na desnoj strani može se aproksimirati s

gdje je slobodni parametar koji se koristi za podešavanje aproksimacije. Na primjer, daje točne rezultate na oba kraja intervala, dok daje optimalnu aproksimaciju (najbolju u smislu uniformne norme pogreške). Međutim, algoritam ne koristi tu vrijednost jer ne uzima u obzir sljedeće korake. desno|mini|Cijeli broj povezan s brojem s pomičnim zarezom (plavom bojom), u usporedbi sa skaliranim i pomaknutim logaritmom (sivom bojom) Dakle, postoji aproksimacija

Interpretacija uzorka bitova s pomičnim zarezom od kao cijeli broj dajeSince is positive, .

Tada se čini da je skalirana i pomaknuta segmentno linearna aproksimacija , kao što je prikazano na slici desno. Drugim riječima, aproksimira se s

Prva aproksimacija rezultata Izračun temelji se na identitetu