forståelse af jordskælvets hurtige Inverse kvadratrod
en artikel og forskningsartikel beskriver en hurtig, tilsyneladende magisk måde at beregne den inverse kvadratrod på ($1/\kvm), der bruges i spillet jordskælv.
jeg er ingen grafikekspert, men værdsætter, hvorfor firkantede rødder er nyttige. Pythagoras sætning beregner afstanden mellem punkter, og opdeling efter afstand hjælper med at normalisere vektorer. (Normalisering er ofte bare en fancy betegnelse for division.)
3D-spil som jordskælv divideres med afstandssillioner (Ja billioner) gange hvert sekund, så “mindre” præstationsforbedringer hjælper enormt. Vi ønsker ikke at tage kvadratroden og opdele den regelmæssige måde: eksponentiering og division er virkelig, virkelig dyre for CPU ‘ en.
i betragtning af disse betingelser er her den magiske formel for at få $1/\kvm$, som fundet i jordskælv (mine kommentarer indsat):
min forståelse: dette utrolige hack estimerer den inverse rod ved hjælp af Nyton ‘ s metode til tilnærmelse og starter med et godt indledende gæt.
for at gætte, tager det flydende punktnummer i videnskabelig notation og negerer & halverer eksponenten for at få noget tæt på den inverse kvadratrod. Det kører derefter en runde af Nyton ‘ s tilnærmelsesmetode for yderligere at forfine estimatet og tada, vi har noget nær den inverse kvadratrod.
Nyton ‘s metode til tilnærmelse
Nyton’ s metode kan bruges til at finde omtrentlige rødder af enhver funktion. Du kan fortsætte med at gentage metoden for at komme tættere og tættere på roden, men denne funktion bruger kun 1 trin! Her er et crash-kursus på Nyton ‘ s metode (det var nyt for mig):
du kan fortsætte med at gentage denne proces (tilslutte dit nye gæt til formlen) og få tættere tilnærmelser til din rod. Til sidst har du et” nyt gæt”, der gør f(nyt gæt) virkelig, virkelig tæt på nul-det er en rod! (Eller tæt nok til regeringsarbejde, som de siger).
det er klart, at vi ønsker at gøre vores fejl så lille som muligt. Det betyder at finde “H”, der gør fejl(H) = 0, hvilket er det samme som at finde roden til fejlligningen. Hvis vi sætter fejl (i) i nyheds tilnærmelsesformel:
og tage de rigtige derivater:
vi kan tilslutte dem for at få formlen til et bedre gæt:
hvilket er præcis ligningen du ser i koden ovenfor, husk at h er vores nye gæt (g) og” halv ” er halvdelen af den oprindelige værdi ($0.5 i$):
x = x*(1.5f - xhalf*x*x);
med denne formel kan vi starte med et gæt “g” og gentage formlen for at få bedre gæt. Prøv denne demo for at bruge flere iterationer til at finde den inverse firkant:
så mine venner bliver spørgsmålet: “Hvordan kan vi lave et godt indledende gæt?”
gør et godt gæt
Hvad er et godt gæt for den inverse kvadratrod? Det er lidt af et trick spørgsmål-vores bedste gæt for den inverse kvadratroden er den inverse kvadratroden selv!
Ok hotshot, du spørger, Hvordan får vi faktisk $1 / \ kvm$?
det er her magien sparker ind. Lad os sige, at du har et tal i eksponentform eller videnskabelig notation:
nu, hvis du vil finde den almindelige kvadratrod, vil du bare dele eksponenten med 2:
og hvis du vil have den inverse kvadratrod, skal du dele eksponenten med -2 for at vende tegnet:
så hvordan kan vi få eksponenten for et tal uden andre dyre operationer?
Floats er gemt i mantissa-eksponent form
Nå, vi er heldige. Flydende punktnumre gemmes af computere i mantissa-eksponentform, så det er muligt at udtrække og opdele eksponenten!
men i stedet for eksplicit at gøre division (dyrt for CPU ‘ en) bruger koden et andet smart hack: det skifter bits. Højre skift med en position er den samme som at dividere med to (Du kan prøve dette for enhver magt på 2, men det vil afkorte resten). Og hvis du vil have et negativt tal, i stedet for at multiplicere med -1 (multiplikationer er dyre), skal du bare trække tallet fra “0” (subtraktioner er billige).
så konverterer koden det flydende punktnummer til et heltal. Det skifter derefter bitene med en, hvilket betyder, at eksponentbitene er divideret med 2 (når vi til sidst vender bitene tilbage til en float). Og endelig, for at negere eksponenten, trækker vi fra det magiske tal 0h5f3759df. Dette gør et par ting: det bevarer mantissen (den ikke-eksponente del, aka 5 i: $5 \cdot 10^6$), håndterer Ulige Lige eksponenter, skifter bits fra eksponenten til mantissen og alle slags funky ting. Papiret har flere detaljer og forklaring, Jeg fangede det ikke første gang. Som altid er du velkommen til at kommentere, hvis du har en bedre forklaring på, hvad der sker.
resultatet er, at vi får en indledende gæt, der er virkelig tæt på den virkelige inverse kvadratrod! Vi kan derefter gøre en enkelt runde af Nyton metode til at forfine gæt. Flere runder er mulige (mod en ekstra beregningsudgift), men en runde er alt, hvad der er nødvendigt for den nødvendige præcision.
så hvorfor det magiske nummer?
det store hack er, hvordan heltal og flydende punktnumre gemmes. Flydende tal som $5.4 \ cdot 10^6$ Gem deres eksponent i et separat interval af bits end “5.4”. Når du skifter hele tallet, deler du eksponenten med 2, samt deler tallet (5.4) med 2 også. Det er her det magiske tal kommer ind — det gør nogle fede korrektioner for denne division, som jeg ikke helt forstår. Der er dog flere magiske tal, der kan bruges-denne sker for at minimere fejlen i mantissen.
det magiske tal korrigerer også for lige/ulige eksponenter; papiret nævner, at du også kan finde andre magiske tal at bruge.
ressourcer
der er yderligere diskussion om reddit (bruger pb_seppelin) og slashdot:
- http://games.slashdot.org/article.pl?sid=06/12/01/184205 og min kommentar
andre indlæg i denne serie
- talsystemer og baser
- den hurtige Guide til GUID ‘ er
- forståelse af jordskælvets hurtige Inverse kvadratrod
- en simpel introduktion til computernetværk
- Skift to variabler ved hjælp af
- forståelse af store og små endian byte order
- Unicode og dig
- lidt Diddy om binære filformater
- sorteringsalgoritmer