Understanding Quake’ s Fast Inverse Square Root
artykuł i praca naukowa opisują szybki, pozornie magiczny sposób obliczania odwrotnego pierwiastka kwadratowego ($1/\sqrt{x}$), używany w grze Quake.
nie jestem ekspertem od grafiki, ale doceniam, dlaczego pierwiastki kwadratowe są przydatne. Twierdzenie Pitagorasa oblicza odległość między punktami, a dzielenie przez odległość pomaga normalizować wektory. (Normalizacja jest często tylko wymyślnym określeniem podziału.)
gry 3D, takie jak Quake, dzielą się przez odległość zillionami (tak zillionami) razy na sekundę, więc „drobne” ulepszenia wydajności pomagają ogromnie. Nie chcemy brać pierwiastka kwadratowego i dzielić go w regularny sposób: wykładnik i dzielenie są bardzo, bardzo drogie dla procesora.
biorąc pod uwagę te warunki, oto magiczna formuła, aby uzyskać $1 / \sqrt{x}$, Jak znaleziono w Quake (Moje komentarze wstawione):
moje zrozumienie: ten niesamowity hack szacuje odwrotność korzenia za pomocą metody Zbliżenia Newtona i zaczyna się od świetnego początkowego zgadywania.
aby zgadnąć, bierze liczbę zmiennoprzecinkową w notacji naukowej i neguje & połowę wykładnika, aby uzyskać coś blisko odwrotnego pierwiastka kwadratowego. Następnie uruchamia metodę aproksymacji Newtona w celu dalszego udoskonalenia estymacji i tada, mamy coś w pobliżu odwrotnego pierwiastka kwadratowego.
metoda przybliżenia Newtona
Metoda Newtona może być użyta do znalezienia przybliżonych pierwiastków dowolnej funkcji. Możesz kontynuować iterację metody, aby zbliżyć się do korzenia, ale ta funkcja używa tylko 1 kroku! Oto crash-kurs metody Newtona (był dla mnie nowy):
możesz powtarzać ten proces (podłączając swój nowy odgadnięcie do formuły)i uzyskać bliższe przybliżenia dla swojego korzenia. W końcu masz „nowe odgadnięcie”, które sprawia, że f (nowe odgadnięcie) jest naprawdę blisko zera – to jest pierwiastek! (Lub wystarczająco blisko do pracy rządowej, jak to mówią).
oczywiście chcemy, aby nasz błąd był jak najmniejszy. Oznacza to znalezienie” x”, które sprawia, że błąd(x) = 0, co jest tym samym, co znalezienie pierwiastka równania błędu. Jeśli wpiszemy błąd (x) do wzoru aproksymacji Newtona:
i weźmy odpowiednie pochodne:
możemy je podłączyć, aby uzyskać formułę dla lepszego zgadywania:
co jest dokładnie równaniem, które widzisz w powyższym kodzie, pamiętając, że x jest naszym nowym domyśleniem (g), A „xhalf” jest połową pierwotnej wartości ($0.5 i$):
x = x*(1.5f - xhalf*x*x);
z tą formułą, możemy zacząć od zgadywania ” g ” i powtórzyć formułę, aby uzyskać lepsze zgadywanie. Wypróbuj to demo, aby użyć wielu iteracji, aby znaleźć kwadrat odwrotny:
więc moi przyjaciele, pytanie brzmi: „jak możemy zrobić dobry początkowy odgadnięcie?”
zgadywanie
co jest dobrym zgadywaniem dla odwrotnego pierwiastka kwadratowego? To trochę podchwytliwe pytanie — naszym najlepszym przypuszczeniem dla odwrotnego pierwiastka kwadratowego jest sam odwrotny pierwiastek kwadratowy!
ok hotshot, pytasz, jak właściwie dostać $1 / \sqrt{x}$?
tu wkracza Magia. Załóżmy, że masz liczbę w postaci wykładnika lub notacji naukowej:
teraz, jeśli chcesz znaleźć regularny pierwiastek kwadratowy, po prostu podzielisz wykładnik przez 2:
a jeśli chcesz odwrotnego pierwiastka kwadratowego, podziel wykładnik przez -2, aby odwrócić znak:
więc jak możemy uzyskać wykładnik liczby bez innych kosztownych operacji?
pływaki są przechowywane w postaci wykładnika mantissa
Cóż, mamy szczęście. Liczby zmiennoprzecinkowe są przechowywane przez komputery w postaci wykładnika mantissa, więc możliwe jest wyodrębnienie i podzielenie wykładnika!
ale zamiast jawnie robić dzielenie (drogie dla procesora), kod wykorzystuje kolejny sprytny hack: przesuwa bity. Przesunięcie w prawo o jedną pozycję jest takie samo jak dzielenie przez dwa (możesz spróbować tego dla dowolnej potęgi 2, ale to skróci resztę). A jeśli chcesz uzyskać liczbę ujemną, zamiast mnożyć przez -1 (mnożenie jest drogie), po prostu odejmij liczbę od „0” (odejmowanie jest tanie).
kod Konwertuje liczbę zmiennoprzecinkową na liczbę całkowitą. Następnie przesuwa bity o jeden, co oznacza, że bity wykładnika są dzielone przez 2 (Kiedy w końcu zamieniamy bity z powrotem w float). I na koniec, aby zanegować wykładnik, odejmujemy od magicznej liczby 0x5f3759df. Robi to kilka rzeczy: zachowuje mantissę (część bez wykładnika, aka 5 W: $5 \cdot 10^6$), obsługuje nieparzyste wykładniki, przesuwa bity z wykładnika do mantissy i wszelkiego rodzaju funky rzeczy. Gazeta ma więcej szczegółów i wyjaśnień, nie złapałem wszystkiego za pierwszym razem. Jak zawsze, nie krępuj się komentować, jeśli masz lepsze wyjaśnienie tego, co się dzieje.
w rezultacie otrzymujemy wstępne przypuszczenie, które jest naprawdę bliskie prawdziwemu odwrotnemu pierwiastkowi kwadratowemu! Następnie możemy wykonać jedną rundę metody Newtona, aby udoskonalić zgadywanie. Więcej rund jest możliwych (przy dodatkowym koszcie obliczeniowym), ale jedna runda to wszystko, co jest potrzebne do uzyskania dokładności.
dlaczego więc magiczna liczba?
wielkim hackiem jest sposób przechowywania liczb całkowitych i zmiennoprzecinkowych. Liczby zmiennoprzecinkowe jak $ 5.4 \ cdot 10^6$ przechowuje ich wykładnik w oddzielnym zakresie bitów niż „5.4”. Kiedy przesuwasz całą liczbę, dzielisz wykładnik przez 2, a także dzieląc liczbę (5.4)przez 2. Tutaj pojawia się magiczna liczba-wprowadza fajne poprawki do tego podziału, których nie do końca rozumiem. Istnieje jednak kilka magicznych liczb, które mogą być użyte – ta zdarza się, aby zminimalizować błąd w modliszce.
magiczna liczba poprawia również wykładniki parzyste / nieparzyste; w artykule wspomniano, że można również znaleźć inne magiczne liczby do użycia.
zasoby
jest dalsza dyskusja na temat Reddita (user pb_zeppelin) i slashdota:
- http://games.slashdot.org/article.pl?sid=06/12/01/184205 i mój komentarz
inne posty z tej serii
- systemy liczbowe i bazy
- krótki przewodnik po GUID
- zrozumienie szybkiego odwrotnego pierwiastka kwadratowego Quake ’ a
- proste wprowadzenie do sieci komputerowej
- Zamień dwie zmienne za pomocą XOR
- zrozumienie dużych i mała endiańska kolejność bajtów
- Unicode i ty
- trochę Diddy o binarnych formatach plików
- algorytmy sortowania