Forstå Quakes Raske Inverse Kvadratrot
en artikkel og forskningspapir beskriver en rask, tilsynelatende magisk måte å beregne den inverse kvadratroten ($1 / \sqrt{x}$), brukt i Spillet Quake.
jeg er ingen grafikkekspert, men setter pris på hvorfor firkantede røtter er nyttige. Pythagoras ‘ læresetning beregner avstand mellom punkter, og dividere med avstand bidrar til å normalisere vektorer. (Normalisering er ofte bare et fancy begrep for divisjon .)
3D-spill som Quake dividere med avstand zillions (ja zillions) ganger hvert sekund, så «mindre» ytelsesforbedringer hjelpe umåtelig. Vi ønsker ikke å ta kvadratroten og dele den vanlige måten: eksponering og divisjon er virkelig, veldig dyrt for CPU.
Gitt disse forholdene, her er den magiske formelen for å få $1/\sqrt{x}$, som funnet I Quake (mine kommentarer satt inn):
Min Forståelse: Denne utrolige hack anslår den inverse roten ved Hjelp Av Newtons tilnærmingsmetode, og starter med en god første gjetning.
for å gjette, tar det flytende punktnummer i vitenskapelig notasjon, og negerer & halverer eksponenten for å få noe nær den inverse kvadratroten. Det kjører da En runde Newtons tilnærmingsmetode for å ytterligere avgrense estimatet og tada, vi har noe nær den inverse kvadratroten.
Newtons Tilnærmingsmetode
Newtons metode kan brukes til å finne omtrentlige røtter av enhver funksjon. Du kan fortsette å iterere metoden for å komme nærmere og nærmere roten, men denne funksjonen bruker bare 1 trinn! Her er et krasjkurs På Newtons metode (det var nytt for meg):
Du kan fortsette å gjenta denne prosessen (plugge inn din nye gjetning i formelen) og komme nærmere tilnærminger for roten din. Til slutt har du en «ny gjetning» som gjør f(ny gjetning) virkelig, veldig nær null-det er en rot! (Eller nær nok for regjeringens arbeid, som de sier).
Klart, vi ønsker å gjøre vår feil så liten som mulig. Det betyr å finne » x » som gjør feil (x) = 0, som er det samme som å finne roten til feilligningen. Hvis vi plugger feil (x) til Newtons tilnærmelsesformel:
og ta de riktige derivatene:
vi kan plugge dem inn for å få formelen for et bedre gjetning:
Som er akkurat ligningen du ser i koden ovenfor, husk at x er vårt nye gjetning (g) og «xhalf» er halvparten av den opprinnelige verdien ($0,5 i$):
x = x*(1.5f - xhalf*x*x);
med denne formelen kan vi starte med en gjetning » g » og gjenta formelen for å få bedre gjetninger. Prøv denne demoen for å bruke flere iterasjoner for å finne den inverse firkanten:
så mine venner, spørsmålet blir: «Hvordan kan Vi lage en god første gjetning?»
Gjør En God Gjetning
Hva er en god gjetning for den inverse kvadratroten? Det er litt av et lurespørsmål-vårt beste gjetning for den inverse kvadratroten er den inverse kvadratroten selv!
Ok hotshot, du spør, hvordan får vi faktisk $1 / \sqrt{x}$?
det er her magien slår inn. La oss si at du har et tall i eksponentform eller vitenskapelig notasjon:
Nå, Hvis du vil finne den vanlige kvadratroten, vil du bare dele eksponenten med 2:
og hvis du vil ha den inverse kvadratroten, del eksponenten med -2 for å vende tegnet:
Så, hvordan kan vi få eksponenten til et tall uten andre dyre operasjoner?
Flyter lagres i mantissa-eksponentform
Vel, vi har lykke til. Flyttall lagres av datamaskiner i mantissa-eksponentform, så det er mulig å trekke ut og dele eksponenten!
men i stedet for eksplisitt å gjøre divisjon (dyrt FOR CPU), bruker koden en annen smart hack: den skifter biter. Rettskifting med en posisjon er den samme som å dele med to(du kan prøve dette for noen kraft på 2, men det vil avkorte resten). Og hvis du vil få et negativt tall, i stedet for å multiplisere med -1 (multiplikasjoner er dyre), trekker du bare tallet fra «0» (subtraksjoner er billige).
så konverterer koden flyttallsnummeret 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 mantissa (ikke-eksponentdelen, aka 5 i: $5 \cdot 10^6$), håndterer odd-even eksponenter, skifter biter fra eksponenten til mantissa, og alle slags funky ting. Papiret har flere detaljer og forklaring, jeg fanget ikke alt i første omgang. Som alltid, gjerne kommentere hvis du har en bedre forklaring på hva som skjer.
resultatet er at vi får en første gjetning som er veldig nær den virkelige inverse kvadratroten! Vi kan da gjøre En enkelt runde Av Newtons metode for å avgrense gjetningen. Flere runder er mulige (på en ekstra beregningskostnad), men en runde er alt som trengs for presisjonen som trengs.
Så hvorfor det magiske tallet?
den store hack er hvordan heltall og flyttall blir lagret. Flytende punkt tall som $5.4 \ cdot 10^6$ lagre eksponenten i et eget utvalg av biter enn «5.4». Når du skifter hele tallet, deler du eksponenten med 2, så vel som å dele tallet (5,4) med 2 også. Det er her det magiske tallet kommer inn-det gjør noen kule rettelser for denne divisjonen, som jeg ikke helt forstår. Det er imidlertid flere magiske tall som kan brukes-dette skjer for å minimere feilen i mantissen.
det magiske tallet korrigerer også for jevne / odde eksponenter; papiret nevner at du også kan finne andre magiske tall å bruke.
Ressurser
det er videre diskusjon om reddit (bruker pb_zeppelin) og slashdot:
- http://games.slashdot.org/article.pl?sid=06/12/01/184205 Og min kommentar
Andre Innlegg I Denne Serien
- Nummersystemer Og Baser
- Hurtigveiledningen Til Guider
- Forstå Quake ‘ S Raske Inverse Kvadratrot
- En Enkel Introduksjon Til Datanettverk
- Bytt to variabler ved HJELP AV XOR
- Forstå Store Og litt endian byte rekkefølge
- unicode og du
- Litt Diddy Om Binære Filformater
- Sorteringsalgoritmer