Fast inverse square root Er en algoritme som anslår 
, den gjensidige (eller multiplikative inverse) av kvadratroten av et 32-biters flyttall x i IEEE 754 flyttallformat. Computing gjensidige kvadratrøtter er nødvendig i mange applikasjoner, for eksempel vektor normalisering i videospill og brukes mest i beregninger involvert I 3D-programmering. I 3d-grafikk brukes overflatenormaler, 3-koordinatvektorer med lengde 1, for å uttrykke belysning og refleksjon. Det var mange overflate normaler. Og beregning av dem innebærer normalisering av mange vektorer. Normalisering er ofte bare et fancy begrep for divisjon. Pythagoras ‘ læresetning beregner avstand mellom punkter, og dividere med avstand hjelper normalisere vektorer: 
denne algoritmen er best kjent for sin implementering i 1999 i kildekoden Til Quake III Arena Game, et førstepersonsskytespill som gjorde stor bruk AV 3D-grafikk. På den tiden, det var generelt beregningsmessig dyrt å beregne gjensidig av et flyttall, spesielt i stor skala; den raske inverse kvadratroten omgått dette trinnet.
Algoritme:
Trinn 1: den tolker biter av flyttallsinngangen som et heltall.
i = * ( long * ) &y;
Trinn 2: Det tar den resulterende verdien og gjør heltall aritmetikk på den som gir en tilnærming av verdien vi leter etter.
i = 0x5f3759df - ( i >> 1 );
Trinn 3: resultatet er ikke tilnærmingen selv, det er et heltall som skjer, hvis du tolker bitene som et flytende punktnummer, tilnærmingen. Så koden gjør omvendt av konverteringen i trinn 1 for å komme tilbake til flyttall:
y = * ( float * ) &i;
Trinn 4: og til slutt kjører det en enkelt iterasjon Av Newtons metode for å forbedre tilnærmingen.
y = y * ( threehalfs - ( x2 * y * y ) ); //threehalfs = 1.5F;
algoritmen aksepterer et 32-biters flyttall som inngang og lagrer en halvert verdi for senere bruk. Ved å behandle bitene som representerer flyttallsnummeret som et 32-biters heltall, utføres et logisk skifte rett ved en bit, og resultatet trekkes fra det magiske tallet 0x5F3759DF. Dette er den første tilnærmingen til den inverse kvadratroten av inngangen. Ved å behandle bitene igjen som et flyttall, kjører Det en iterasjon Av Newtons tilnærmingsmetode, noe som gir en mer presis tilnærming.
La oss si at det er et tall i eksponentform eller vitenskapelig notasjon:
=100 millioner
Nå, for å finne den vanlige kvadratroten, vil vi bare dele eksponenten med 2:
og hvis du vil vite den inverse kvadratroten, divider eksponenten med -2 for å vende tegnet:
så konverterer koden det flytende punktnummeret til et heltall. Det skifter deretter bitene med en, noe som betyr at eksponentbitene er delt med 2 (når vi til slutt slår bitene tilbake i en flyte). Og til slutt, for å negere eksponenten, trekker vi fra det magiske tallet 0x5f3759df. Dette gjør noen ting: det bevarer mantissen (den ikke-eksponentdelen, aka 5 i: 5 · 
), håndterer odd-even eksponenter, skiftende biter fra eksponenten inn i mantissa, og alle slags funky ting.
følgende kode er den raske inverse kvadratroten implementering Fra Quake III Arena (eksakt original kommentar skrevet I Quake III Arena Spillet).
#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; } Utgang:
