Understanding Quake’ s Fast Inverse Square Root
en artikel och forskningspapper beskriver ett snabbt, till synes magiskt sätt att beräkna den inverse kvadratroten ($1/\sqrt{x}$), som används i spelet Quake.
jag är ingen grafikexpert, men uppskattar varför kvadratrötter är användbara. Pythagoras sats beräknar avståndet mellan punkter, och delning med avstånd hjälper till att normalisera vektorer. (Normalisering är ofta bara en fin term för division.)
3D-spel som Quake divide med avstånd zillioner (ja zillioner) gånger varje sekund, så ”mindre” prestandaförbättringar hjälper oerhört. Vi vill inte ta kvadratroten och dela det vanliga sättet: exponentiering och division är verkligen, riktigt dyra för CPU.
med tanke på dessa villkor är här den magiska formeln för att få $1/\sqrt{x}$, som finns i Quake (mina kommentarer infogade):
min förståelse: denna otroliga hack uppskattar den inversa roten med Newtons approximationsmetod och börjar med en stor initial gissning.
för att gissa, tar det flytande punktnummer i vetenskaplig notation och negerar & halverar exponenten för att få något nära den inversa kvadratroten. Den kör sedan en runda av Newtons approximationsmetod för att ytterligare förfina uppskattningen och tada, vi har något nära den inversa kvadratroten.
Newtons metod för Approximation
Newtons metod kan användas för att hitta ungefärliga rötter av vilken funktion som helst. Du kan fortsätta iterera metoden för att komma närmare och närmare roten, men den här funktionen använder bara 1 steg! Här är en kraschkurs på Newtons metod (det var nytt för mig):
du kan fortsätta att upprepa denna process (koppla in din nya gissning i formeln) och få närmare approximationer för din rot. Så småningom har du en ”ny gissning” som gör f(ny gissning) verkligen, verkligen nära noll-det är en rot! (Eller tillräckligt nära för regeringsarbete, som de säger).
det är uppenbart att vi vill göra vårt fel så litet som möjligt. Det betyder att hitta ” x ” som gör fel(x) = 0, vilket är detsamma som att hitta roten till felekvationen. Om vi ansluter fel (x) till Newtons approximationsformel:
och ta rätt derivat:
vi kan koppla in dem för att få formeln för en bättre gissning:
vilket är exakt den ekvation du ser i koden ovan, kom ihåg att x är vår nya gissning (g) och ”xhalf” är hälften av det ursprungliga värdet ($0.5 i$):
x = x*(1.5f - xhalf*x*x);
med denna formel kan vi börja med en gissning” g ” och upprepa formeln för att få bättre gissningar. Prova denna demo för att använda flera iterationer för att hitta den inversa torget:
så mina vänner blir frågan: ”Hur kan vi göra en bra första gissning?”
gör en bra gissning
Vad är en bra gissning för den inversa kvadratroten? Det är lite av en trickfråga-vår bästa gissning för den inversa kvadratroten är den inversa kvadratroten själv!
Ok hotshot, du frågar, Hur får vi faktiskt $1 / \ sqrt{x}$?
det är här magin sparkar in. Låt oss säga att du har ett tal i exponentform eller vetenskaplig notation:
nu, om du vill hitta den vanliga kvadratroten, skulle du bara dela exponenten med 2:
och om du vill ha den inversa kvadratroten, dela exponenten med -2 för att vända tecknet:
så, hur kan vi få exponenten för ett tal utan andra dyra operationer?
Floats lagras i mantissa-exponentform
Tja, vi har tur. Flytpunktsnummer lagras av datorer i mantissa-exponentform, så det är möjligt att extrahera och dela exponenten!
men istället för att uttryckligen göra division (dyrt för CPU) använder koden ett annat smart hack: det skiftar bitar. Högerskiftning med en position är densamma som att dela med två (Du kan prova detta för någon kraft på 2, men det kommer att trunkera resten). Och om du vill få ett negativt tal, istället för att multiplicera med -1 (multiplikationer är dyra), subtrahera bara numret från ”0” (subtraktioner är billiga).
så konverterar koden flyttalsnumret till ett heltal. Det skiftar sedan bitarna med en, vilket innebär att exponentbitarna delas med 2 (när vi så småningom vänder bitarna tillbaka till en flottör). Och slutligen, för att negera exponenten, subtraherar vi från det magiska numret 0x5f3759df. Detta gör några saker: det bevarar mantissa (den icke-exponentdelen, aka 5 in: $5 \cdot 10^6$), hanterar Udda Jämn exponenter, skiftar bitar från exponenten till mantissa och alla slags funky saker. Papperet har mer detaljer och förklaring, Jag fångade inte allt det första gången. Som alltid, gärna kommentera om du har en bättre förklaring av vad som händer.
resultatet är att vi får en första gissning som är riktigt nära den verkliga inversa kvadratroten! Vi kan sedan göra en enda omgång av Newtons metod för att förfina gissningen. Fler rundor är möjliga (till en extra beräkningskostnad), men en runda är allt som behövs för den precision som behövs.
så, varför det magiska numret?
The great hack är hur heltal och flyttal lagras. Flyttal som $5.4 \ cdot 10^6 $ lagra sin exponent i ett separat intervall av bitar än”5.4″. När du flyttar hela numret delar du exponenten med 2, samt delar numret (5.4) med 2 också. Det är här det magiska numret kommer in-det gör några coola korrigeringar för denna division, som jag inte riktigt förstår. Det finns dock flera magiska nummer som kan användas-det här händer för att minimera felet i mantissa.
det magiska numret korrigerar också för jämn/udda exponenter; papperet nämner att du också kan hitta andra magiska nummer att använda.
resurser
det finns ytterligare diskussion om reddit (användare pb_zeppelin) och slashdot:
- http://games.slashdot.org/article.pl?sid=06/12/01/184205 och min kommentar
andra inlägg i denna serie
- nummersystem och baser
- snabbguiden till GUIDs
- förstå quakes snabba inversa kvadratrot
- en enkel introduktion till datornätverk
- byt två variabler med XOR
- förstå stora och stora little endian byte order
- Unicode och du
- en liten Diddy om binära filformat
- sorteringsalgoritmer