Pochopení Quake Rychle Inverzní Odmocnina
článek a výzkum papíru popsat, rychle, zdánlivě magické způsob, jak vypočítat inverzní odmocnina ($1/\sqrt{x}$), který se používá ve hře Quake.
nejsem odborník na grafiku, ale oceňuji, proč jsou odmocniny užitečné. Pythagorova věta počítá vzdálenost mezi body a dělení vzdáleností pomáhá normalizovat vektory. (Normalizace je často jen efektní termín pro dělení.)
3D hry jako Quake dělí vzdálenost zillions (Ano zillions) časů každou sekundu, takže“ drobné “ vylepšení výkonu pomáhají nesmírně. Nechceme vzít druhou odmocninu a rozdělit pravidelnou cestu: umocnění a dělení jsou pro CPU opravdu drahé.
Vzhledem k tomu, tyto podmínky, tu je kouzelná formule získat $1/\sqrt{x}$, jak bylo zjištěno v Quake (můj komentář vložen):
Moje Chápání: Tento neuvěřitelný hack odhady inverzní root pomocí newtonovy metody aproximace, a začne s velkou počáteční odhad.
Chcete-li odhadnout, to trvá plovoucí desetinnou čárkou číslo ve vědecké notaci, a neguje & poloviny exponent dostat něco blízko inverzní druhá odmocnina. To pak běží kolo Newtonovy aproximační metody pro další upřesnění odhadu a Tada, máme něco blízko inverzní druhé odmocniny.
Newtonova metoda aproximace
Newtonova metoda může být použita k nalezení přibližných kořenů jakékoli funkce. Můžete pokračovat v iteraci metody, abyste se přiblížili a přiblížili ke kořenu, ale tato funkce používá pouze 1 krok! Zde je rychlokurz o Newtonově metodě (bylo to pro mě nové):
tento proces můžete opakovat (zapojením nového odhadu do vzorce)a získat bližší aproximace kořenového adresáře. Nakonec máte „nový odhad“, který dělá f (nový odhad) opravdu, opravdu blízko nuly – je to kořen! (Nebo dost blízko pro vládní práci, jak se říká).
je zřejmé, že chceme, aby naše chyba byla co nejmenší. To znamená Najít „x“, které dělá chybu(x) = 0, což je stejné jako nalezení kořene chybové rovnice. Pokud bychom plug chybu(x) do Newtonova aproximační vzorec:
a vzít správné deriváty:
můžeme zapojit na ten vzorec pro lepší odhad:
Což je přesně rovnice můžete vidět v kódu výše, připomenout, že x je náš nový odhad (g) a „xhalf“ je polovina původní hodnoty ($0.5 já$):
x = x*(1.5f - xhalf*x*x);
S tímto vzorcem, můžeme začít hádat, „g“ a opakovat vzorce, získat lepší odhady. Zkuste toto demo pro použití více iterací najít inverzní čtverec:
takže moji přátelé, otázka se stává: „jak můžeme udělat dobrý počáteční odhad?“
dobrý odhad
jaký je dobrý odhad pro inverzní druhou odmocninu? Je to trochu chyták-náš nejlepší odhad pro inverzní druhou odmocninu je inverzní druhá odmocnina sama!
Ok hotshot, ptáte se, jak vlastně dostaneme $1 / \ sqrt{x}$?
to je místo, kde magie kopy. Řekněme, že máte číslo v exponentní formě nebo vědecké notaci:
Nyní, pokud chcete najít pravidelný odmocninu, jen rozdělit exponent o 2:
A pokud chcete, inverzní odmocnina, rozdělit tím, že exponent -2 otočit ceduli:
Takže, jak se můžeme dostat exponent řada bez jiné drahé operace?
plováky jsou uloženy ve formě mantissa-exponent
No, máme štěstí. Čísla s plovoucí desetinnou čárkou jsou uloženy v počítačích ve formě mantissa-exponent, takže je možné extrahovat a rozdělit exponent!
ale místo explicitního dělení (drahé pro CPU) používá kód další chytrý hack: posune bity. Posun doprava o jednu pozici je stejný jako dělení dvěma (můžete to zkusit pro libovolnou sílu 2, ale zbytek zkrátí). A pokud chcete získat záporné číslo, namísto násobení -1 (násobení je drahé), jednoduše odečtěte číslo od “ 0 “ (odčítání je levné).
takže kód převede číslo s plovoucí desetinnou čárkou na celé číslo. To pak posune bity o jeden, což znamená, že exponent bity jsou děleny 2 (Když jsme nakonec zase bity zpět do plováku). A konečně, abychom negovali exponent, odečteme od magického čísla 0x5f3759df. To znamená několik věcí: zachovává mantisa (non-exponent část, aka 5 in: $5 \cdot 10^6$), kliky liché sudé exponenty, řazení bitů z exponent do mantisy, a všechny druhy funky věci. Papír má více podrobností a vysvětlení, nezachytil jsem to všechno napoprvé. Jako vždy, neváhejte komentovat, pokud máte lepší vysvětlení toho, co se děje.
výsledkem je, že dostaneme počáteční odhad, který je opravdu blízko skutečné inverzní druhé odmocniny! Pak můžeme udělat jedno kolo Newtonovy metody, abychom upřesnili odhad. Je možné více kol (za další výpočetní náklady), ale jedno kolo je vše, co je potřeba pro potřebnou přesnost.
tak proč magické číslo?
skvělý hack je, jak jsou uložena celá čísla a čísla s plovoucí desetinnou čárkou. Čísla s plovoucí desetinnou čárkou jako 5 dolarů.4 \ cdot 10^6$ ukládat jejich exponent v samostatném rozsahu bitů než „5.4“. Když posunete celé číslo, vydělíte exponent 2 a vydělíte číslo (5.4) také 2. To je místo, kde přichází magické číslo — dělá nějaké skvělé opravy pro toto rozdělení, které úplně nerozumím. Existuje však několik magických čísel , která by mohla být použita-toto se stane, aby se minimalizovala chyba v mantise.
magické číslo také koriguje sudé / liché exponenty; papír zmiňuje, že můžete také najít další magická čísla, která chcete použít.
Zdroje
Tady je další diskuze na redditu (uživatelská pb_zeppelin) a slashdot:
- http://games.slashdot.org/article.pl?sid=06/12/01/184205 a můj komentář
Další Příspěvky V Této Sérii
- Počet Systémů a Základy
- Rychlý Průvodce Guid
- Pochopení Quake Rychle Inverzní Odmocnina
- Jednoduchý Úvod Do Počítačových Sítí
- Prohodit dvě proměnné pomocí XOR
- Porozumění Big a Little Endian Byte Order
- Unicode
- malý diddy o binární formáty souborů
- Třídící Algoritmy