Understanding Quake’ s Fast Inverse Square Root

BY admin

| 20 elokuun, 2021

artikkeli ja tutkimus kuvaavat nopeaa, näennäisesti maagista tapaa laskea Käänteinen neliöjuuri ($1/\sqrt{x}$), jota käytetään pelissä Quake.

en ole mikään grafiikan asiantuntija, mutta ymmärrän, miksi neliöjuuret ovat hyödyllisiä. Pythagoraan lause laskee pisteiden väliset etäisyydet, ja jakamalla etäisyys auttaa normalisoimaan vektoreita. (Normalisointi on usein vain hieno termi jaolle.)

3D-pelit kuten Quake jakavat etäisyyden zillions (Kyllä zillions) kertaa sekunnissa, joten ”pienet” suoritusparannukset auttavat suunnattomasti. Emme halua ottaa neliöjuurta ja jakaa säännönmukaisesti: eksponentaatio ja jako ovat todella, todella kalliita suorittimelle.

näissä olosuhteissa, tässä maaginen kaava saada $1/\sqrt{x}$, kuten löytyy Quake (kommenttini lisätty):

Ymmärtämykseni: tämä uskomaton hack arvioi käänteisen juuren käyttäen Newtonin likiarvomenetelmää, ja alkaa suurella alustavalla arvauksella.

arvauksen tekemiseksi tarvitaan tieteellisessä notaatiossa liukulukuluku, ja nollaa & puolittaa eksponentti, jotta saadaan jotain lähelle käänteistä neliöjuurta. Sitten se juoksee kierroksen Newtonin approksimaatiomenetelmää tarkentaakseen estimaattia ja tada, meillä on jotain lähellä käänteistä neliöjuurta.

Newtonin Likiarvomenetelmää

Newtonin menetelmää voidaan käyttää minkä tahansa funktion likimääräisten juurien etsimiseen. Voit pitää iteroimalla menetelmää päästä lähemmäksi juurta, mutta tämä toiminto käyttää vain 1 vaihe! Tässä on crash-kurssi Newtonin menetelmä (se oli uusi minulle):

voit pitää toistaa tämän prosessin (kytkemällä Uusi arvata kaava) ja saada lähempänä likiarvot Oman root. Lopulta sinulla on ”uusi arvaus”, joka tekee f: stä(uudesta arvauksesta) todella, todella lähellä nollaa-se on juuri! (Tai tarpeeksi lähellä hallituksen työtä, kuten sanotaan).

on selvää, että haluamme tehdä virheemme mahdollisimman pieneksi. Se tarkoittaa sen ”x”: n löytämistä, joka tekee virheen(x) = 0, joka on sama kuin löytäisi virheyhtälön juuren. Jos pistämme virheen (x) Newtonin approksimaatiokaavaan:

ja ottaa oikea johdannaiset:

voimme kytkeä ne, jotta saamme kaavan parempaan arvaukseen.:

mikä on täsmälleen yhtälö näet koodin edellä, muistaa, että x on meidän uusi arvaus (g) ja ”xhalf” on puolet alkuperäisestä arvosta ($0.5 i$):

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

tällä kaavalla voimme aloittaa arvauksella ” g ” ja toistaa kaavan saadaksemme parempia arvauksia. Kokeile tätä demoa käyttämällä useita iteraatioita käänteisen neliön löytämiseksi:

joten ystäväni, kysymys kuuluu: ”miten voimme tehdä hyvän alustavan arvauksen?”

hyvän arvauksen tekeminen

mikä on hyvä arvaus käänteiselle neliöjuurelle? Se on vähän kompakysymys — paras arvauksemme käänteiselle neliöjuurelle on itse käänteiselle neliöjuurelle!

Ok hotshot, kysyt, miten oikeasti saamme $1 / \sqrt{x}$?

tässä kohtaa taika iskee. Oletetaan, että sinulla on luku eksponenttimuodossa tai tieteellisessä notaatiossa:

jos haluat löytää säännöllisen neliöjuuren, jakaisit eksponentin 2:

ja jos haluat käänteisen neliöjuuren, Jaa eksponentti -2: lla kääntääksesi merkin:

Joten, miten voimme saada eksponentti numero ilman muita kalliita operaatioita?

kellukkeet on säilytetty mantissa-eksponenttimuodossa

No, olemme onnekkaita. Tietokoneet tallentavat liukulukuluvut mantissa-eksponenttimuodossa,joten eksponentti on mahdollista purkaa ja jakaa!

mutta eksplisiittisen jaon (suorittimelle kallis) sijaan koodi käyttää toista näppärää hakkerointia: se siirtää bittejä. Oikeanpuoleinen siirtyminen yhdellä paikalla on sama kuin jakamalla kahdella (voit kokeilla tätä mille tahansa potenssille 2, mutta se katkaisee loput). Ja jos halutaan saada negatiivinen luku, sen sijaan että kerrottaisiin -1: llä (kerrannaiset ovat kalliita), vähennetään vain luku ”0”: sta (vähennykset ovat halpoja).

eli koodi muuntaa liukulukuluvun kokonaisluvuksi. Se sitten siirtää bitit yhdellä, mikä tarkoittaa eksponenttibitit jaetaan 2: lla (kun lopulta muutamme bitit takaisin floatiksi). Ja lopuksi, mitätöidäksemme eksponentin, vähennämme taikaluvusta 0x5f3759df. Tämä tekee muutamia asioita: se säilyttää mantissan (ei-eksponentti osa, aka 5 in: $5 \cdot 10^6$), käsittelee parittomia eksponentteja, siirtää bittejä eksponentista mantissaan, ja kaikenlaisia funky tavaraa. Lehdessä on enemmän yksityiskohtia ja selitys, en saanut kaikkea kiinni ensimmäisellä kerralla. Kuten aina, voit vapaasti kommentoida, jos sinulla on parempi selitys siitä, mitä tapahtuu.

tuloksena saadaan alustava arvaus, joka on todella lähellä todellista käänteistä neliöjuurta! Voimme sitten tehdä yhden kierroksen Newtonin menetelmällä tarkentaa arvausta. Useampi kierros on mahdollinen (laskennallisella lisähinnalla), mutta yksi kierros riittää tarvittavaan tarkkuuteen.

joten, miksi maaginen luku?

suuri hakkerointi on kokonaislukujen ja liukulukujen tallentaminen. Liukulukuluvut, kuten 5 dollaria.4 \cdot 10^6$ tallentaa eksponenttinsa erilliselle bittialueelle kuin ”5.4”. Kun siirrät koko lukua, jaat eksponentin 2: lla, sekä jaat luvun (5,4) myös 2: lla. Tässä kohtaa maaginen numero tulee kuvaan — se tekee siistejä korjauksia tähän jakoon, joita en oikein ymmärrä. On kuitenkin olemassa useita taikalukuja, joita voitaisiin käyttää — tämä sattuu minimoimaan mantissan virheen.

taikaluku korjaa myös parilliset/parittomat eksponentit; lehdessä mainitaan, että muitakin taikalukuja voi käyttää.

resurssit

Redditissä (käyttäjä pb_zeppelin) ja slashdot:

http://games.slashdot.org/article.pl?sid=06/12/01/184205 and my comment