înțelegerea Quake’ s fast Inverse Square Root
un articol și o lucrare de cercetare descrie un mod rapid, aparent Magic pentru a calcula rădăcina pătrată inversă ($1/\sqrt{x}$), utilizate în Quake joc.
nu sunt expert în grafică, dar apreciez de ce rădăcinile pătrate sunt utile. Teorema lui Pitagora calculează distanța dintre puncte, iar împărțirea la distanță ajută la normalizarea vectorilor. (Normalizarea este adesea doar un termen fantezist pentru diviziune.)
Jocuri 3D, cum ar fi Quake divide de zillions distanță (da zillions) de ori în fiecare secundă, astfel încât îmbunătățirile de performanță „minore” ajuta foarte mult. Nu vrem să luăm rădăcina pătrată și Să împărțim modul obișnuit: exponențierea și divizarea sunt foarte, foarte scumpe pentru CPU.
având în vedere aceste condiții, iată formula magică pentru a obține $1/\sqrt{x}$, așa cum se găsește în Quake (comentariile mele inserate):
înțelegerea mea: acest hack incredibil estimează rădăcina inversă folosind metoda de aproximare a lui Newton și începe cu o presupunere inițială excelentă.
pentru a face presupunerea, este nevoie de un număr în virgulă mobilă în notație științifică și neagă & înjumătățește exponentul pentru a obține ceva aproape de rădăcina pătrată inversă. Apoi rulează o rundă a metodei de aproximare a lui Newton pentru a rafina în continuare estimarea și tada, avem ceva aproape de rădăcina pătrată inversă.
metoda lui Newton de aproximare
metoda lui Newton poate fi utilizată pentru a găsi rădăcinile aproximative ale oricărei funcții. Puteți continua să iterați metoda pentru a vă apropia din ce în ce mai mult de rădăcină, dar această funcție folosește doar 1 pas! Iată un crash-curs pe metoda lui Newton (a fost nou pentru mine):
puteți continua să repetați acest proces (conectându-vă Noua presupunere în formulă) și obțineți aproximări mai apropiate pentru rădăcina dvs. În cele din urmă aveți o „nouă presupunere” care face ca f(new guess) să fie într-adevăr, foarte aproape de zero-este o rădăcină! (Sau suficient de aproape pentru munca guvernamentală, cum se spune).
în mod clar, vrem să facem eroarea noastră cât mai mică posibil. Asta înseamnă găsirea „x” care face eroare(x) = 0, care este aceeași cu găsirea rădăcinii ecuației de eroare. Dacă conectăm eroarea (x) la formula de aproximare a lui Newton:
și să ia derivatele corespunzătoare:
le putem conecta pentru a obține formula pentru o presupunere mai bună:
care este exact ecuația pe care o vedeți în codul de mai sus, amintindu-vă că x este noua noastră presupunere (g) și „xhalf” este jumătate din valoarea inițială ($0.5 i$):
x = x*(1.5f - xhalf*x*x);
cu această formulă, putem începe cu o presupunere” g ” și repetați formula pentru a obține presupuneri mai bune. Încercați această demonstrație pentru utilizarea mai multor iterații pentru a găsi pătratul invers:
deci, prietenii mei, întrebarea devine: „cum putem face o presupunere inițială bună?”
făcând o presupunere bună
ce este o presupunere bună pentru rădăcina pătrată inversă? Este un pic de o întrebare capcană-cea mai bună presupunere pentru rădăcina pătrată inversă este rădăcina pătrată inversă în sine!
OK hotshot, vă întreb, cum putem obține de fapt $1 / \ sqrt{x}$?
aici intervine magia. Să presupunem că aveți un număr în formă exponentă sau notație științifică:
acum, dacă doriți să găsiți rădăcina pătrată obișnuită, ați împărți exponentul la 2:
și dacă doriți rădăcina pătrată inversă, împărțiți exponentul cu -2 pentru a răsturna semnul:
Deci, cum putem obține exponentul unui număr fără alte operațiuni costisitoare?
flotoarele sunt stocate în formă de mantisă-exponent
Ei bine, avem noroc. Numerele în virgulă mobilă sunt stocate de computere în formă mantisă-exponent, astfel încât este posibil pentru a extrage și împărți exponentul!
dar în loc să facă în mod explicit diviziunea (costisitoare pentru CPU), codul folosește un alt hack inteligent: schimbă biți. Deplasarea la dreapta cu o poziție este aceeași cu împărțirea la două (puteți încerca acest lucru pentru orice putere de 2, dar va trunchia restul). Și dacă doriți să obțineți un număr negativ, în loc să înmulțiți cu -1 (Înmulțirile sunt scumpe), trebuie doar să scădeți numărul din „0” (scăderile sunt ieftine).
deci, codul convertește numărul în virgulă mobilă într-un număr întreg. Apoi schimbă biții cu unul, ceea ce înseamnă că biții exponenți sunt împărțiți la 2 (când în cele din urmă transformăm biții înapoi într-un flotor). Și, în sfârșit, pentru a nega exponentul, scădem din numărul magic 0x5f3759df. Acest lucru face câteva lucruri: păstrează mantisa (partea non-exponentă, aka 5 în: $5 \cdot 10^6$), gestionează exponenți impari, schimbând biți de la exponent în mantisă și tot felul de lucruri funky. Lucrarea are mai multe detalii și explicații, nu am prins totul prima dată. Ca întotdeauna, nu ezitați să comentați dacă aveți o explicație mai bună a ceea ce se întâmplă.
rezultatul este că obținem o presupunere inițială care este foarte aproape de rădăcina pătrată inversă reală! Putem face apoi o singură rundă a metodei lui Newton pentru a rafina presupunerea. Mai multe runde sunt posibile (la o cheltuială suplimentară de calcul), dar o rundă este tot ceea ce este necesar pentru precizia necesară.
deci, de ce numărul magic?
marele hack este modul în care sunt stocate numere întregi și numere în virgulă mobilă. Numere în virgulă mobilă, cum ar fi $5.4 \ cdot 10 ^ 6 $ stoca exponentul lor într-un interval separat de biți decât „5.4”. Când schimbați întregul număr, împărțiți exponentul la 2, precum și împărțirea numărului (5.4) la 2. Acest lucru este în cazul în care numărul magic vine în — face unele corecții rece pentru această divizie, că eu nu prea înțeleg. Cu toate acestea, există mai multe numere magice care ar putea fi folosite-aceasta se întâmplă pentru a minimiza eroarea în mantisă.
numărul magic corectează, de asemenea, exponenții par/impari; lucrarea menționează că puteți găsi și alte numere magice de utilizat.
resurse
există discuții suplimentare pe reddit (utilizator pb_zeppelin) și slashdot:
- http://games.slashdot.org/article.pl?sid=06/12/01/184205 și comentariul meu
alte posturi din această serie
- sisteme de numere și baze
- Ghidul rapid pentru GUIDs
- înțelegerea Quake rapid invers rădăcină pătrată
- o simplă introducere în rețele de calculatoare
- Swap două variabile folosind XOR
- înțelegerea mare și Little Endian byte order
- Unicode și tu
- un pic Diddy despre formatele de fișiere binare
- algoritmi de sortare