Quake’ s Fast Inverse vierkantswortel

een artikel en onderzoekspaper beschrijven een snelle, schijnbaar magische manier om de inverse vierkantswortel ($1/\sqrt{x}$), gebruikt in het spel Quake te berekenen.

ik ben geen grafisch expert, maar begrijp waarom vierkante wortels nuttig zijn. De stelling van Pythagoras berekent de afstand tussen punten, en delen door afstand helpt bij het normaliseren van vectoren. (Normaliseren is vaak gewoon een mooie term voor deling.)

3D games zoals Quake delivery by distance zillions (Ja zillions) keer per seconde, dus “kleine” prestatieverbeteringen helpen enorm. We willen niet de vierkantswortel nemen en de reguliere manier delen: exponentiatie en deling zijn echt, echt duur voor de CPU.

onder deze voorwaarden, hier is de magische formule om $1/\sqrt{x}$ te krijgen, zoals gevonden in Quake (mijn commentaar ingevoegd):

mijn begrip: deze ongelooflijke hack schat de inverse root met behulp van Newton ‘ s methode van benadering, en begint met een grote eerste gok.

om de gok te maken, neemt het floating-point getal in wetenschappelijke notatie, en negeert & de exponent om iets te krijgen dicht bij de de inverse vierkantswortel. Het draait dan een ronde van Newton ‘ s benadering methode om de schatting verder te verfijnen en tada, we hebben iets in de buurt van de inverse vierkantswortel.

Newton ’s methode van benadering

Newton’ s methode kan worden gebruikt om de wortels van elke functie bij benadering te vinden. Je kunt de methode blijven herhalen om dichter en dichter bij de root te komen, maar deze functie gebruikt slechts 1 stap! Hier is een crash-cursus over Newton ‘ s methode (het was nieuw voor mij):

je kunt dit proces blijven herhalen (je nieuwe gok inpluggen in de formule) en dichter benaderen voor je root. Uiteindelijk heb je een” nieuwe gok ” die f(nieuwe gok) echt, echt dicht bij nul maakt — het is een wortel! (Of dicht genoeg voor overheidswerk, zoals ze zeggen).

het is duidelijk dat we onze fout zo klein mogelijk willen maken. Dat betekent het vinden van de” x ” die fout(x) = 0 maakt, wat hetzelfde is als het vinden van de wortel van de foutvergelijking. Als we de stekker fout(x) in Newton ‘ s benaderingsformule:

en neem de juiste derivaten:

we kunnen steek ze in om de formule voor een betere gok:

en Dat is precies de vergelijking zie je in de code hierboven, eraan te herinneren dat x is onze nieuwe raden (g) en “xhalf” is de helft van de oorspronkelijke waarde ($0.5 ik$):

x = x*(1.5f - xhalf*x*x);

Met deze formule kunnen we starten met een gok “g” en herhaal de formule om betere schattingen. Probeer deze demo voor het gebruik van meerdere iteraties om het inverse kwadraat te vinden:

dus mijn vrienden, de vraag wordt: “hoe kunnen we een goede eerste gok maken?”

een goede gok maken

Wat is een goede gok voor de inverse vierkantswortel? Het is een beetje een strikvraag — onze beste gok voor de inverse vierkantswortel is de inverse vierkantswortel zelf!

OK hotshot, je vraagt, hoe krijgen we eigenlijk $1/\sqrt{x}$?

Dit is waar de magie begint. Laten we zeggen dat je een getal hebt in exponentvorm of wetenschappelijke notatie:

als je de gewone vierkantswortel wilt vinden, deel je de exponent door 2:

en als je de inverse vierkantswortel wilt, deel dan de exponent door -2 om het teken om te draaien:

dus, hoe kunnen we de exponent van een getal krijgen zonder andere dure operaties?

Floats worden opgeslagen in mantissa-exponent vorm

Nou, we hebben geluk. Floating-point getallen worden door computers opgeslagen in mantissa-exponent vorm, dus het is mogelijk om de exponent te extraheren en te delen!

maar in plaats van expliciet delen (duur voor de CPU), gebruikt de code een andere slimme hack: het verschuift bits. Rechts verschuiven door één positie is hetzelfde als delen door twee (Je kunt dit proberen voor elke macht van 2, maar het zal de rest afkappen). En als je een negatief getal wilt krijgen, in plaats van te vermenigvuldigen met -1 (vermenigvuldigingen zijn duur), trek je het getal af van “0” (Aftrekken is goedkoop).

de code zet het floating-point getal om in een geheel getal. Het verschuift dan de bits met een, wat betekent dat de exponent bits worden gedeeld door 2 (Wanneer we uiteindelijk de bits terug te zetten in een float). En tot slot, om de exponent te ontkennen, trekken we af van het magische getal 0x5f3759df. Dit doet een paar dingen: het behoudt de mantissa (het niet-exponent deel, aka 5 in: $5 \cdot 10^6$), behandelt Oneven-even exponenten, verschuift bits van de exponent naar de mantissa, en allerlei funky dingen. De krant heeft meer details en uitleg, Ik heb niet alles van de eerste keer rond vangen. Zoals altijd, voel je vrij om commentaar te geven als je een betere uitleg hebt van wat er gebeurt.

het resultaat is dat we een eerste gok krijgen die echt dicht bij de echte inverse vierkantswortel ligt! We kunnen dan een enkele ronde van Newton ‘ s methode doen om de gok te verfijnen. Meer rondes zijn mogelijk (tegen extra rekenkosten), maar één ronde is alles wat nodig is voor de precisie die nodig is.

dus, waarom het magische getal?

de grote hack is hoe gehele getallen en floating-point getallen worden opgeslagen. Floating-point getallen zoals $ 5.4 \ cdot 10^6$ slaan hun exponent op in een aparte reeks bits dan “5.4”. Wanneer je het gehele getal verschuift, deel je de exponent door 2, en deel je ook het getal (5.4) door 2. Dit is waar het magische getal een rol speelt — het doet een aantal coole correcties voor deze verdeling, die ik niet helemaal begrijp. Er zijn echter verschillende magische getallen die gebruikt kunnen worden — deze is toevallig om de fout in de bidsprinkhaan te minimaliseren.

het magische getal corrigeert ook voor even / oneven exponenten; het papier vermeldt dat u ook andere magische getallen kunt vinden om te gebruiken.

Hulpmiddelen

Er is verdere discussie op reddit (gebruiker pb_zeppelin) en slashdot:

• http://games.slashdot.org/article.pl?sid=06/12/01/184205 en mijn opmerking

Andere Berichten In Deze Serie

1. Aantal Systemen en Basen
2. De Quick Guide to-Guid ‘ s
3. het Begrijpen van Quake is Snel Inverse Square Root
4. Een Eenvoudige Introductie van Computer Netwerken
5. Swap twee variabelen met behulp van XOR
6. het Begrijpen van Big en Little Endian Byte Order
7. Unicode en U
8. Een beetje diddy over binaire bestandsindelingen
9. Sorteer-Algoritmen