Szybka odwrotność pierwiastka kwadratowego
Z Wikipedii, wolnej encyclopedia
Szybka odwrotność pierwiastka kwadratowego, czasami określana jako szybki InvSqrt() lub przez stałą szesnastkową 0x5f3759df – metoda obliczania odwrotności pierwiastka kwadratowego z 32-bitowej liczby zmiennoprzecinkowej w standardzie IEEE 754. Algorytm został prawdopodobnie opracowany w Silicon Graphics na początku lat 90. XX wieku, a jedna z jego implementacji pojawiła się w 1999 roku w kodzie źródłowym gry Quake III: Arena, lecz metoda nie pojawiła się na forach publicznych, takich jak Usenet aż do roku 2002 lub 2003[1] . W ówczesnym czasie podstawowa zaleta algorytmu polegała na unikaniu kosztownych obliczeniowo operacji zmiennoprzecinkowych na korzyść operacji na liczbach całkowitych. Odwrotności pierwiastków kwadratowych są używane do obliczania kątów padania i odbicia dla oświetlenia i cieniowania w grafice komputerowej.
Algorytm na wejściu przyjmuje dodatnią 32-bitową liczbę zmiennoprzecinkową i zachowuje jej połowę do późniejszego wykorzystania. Następnie, interpretując bitową reprezentację liczby zmiennoprzecinkowej jako 32-bitową liczbę całkowitą, dokonuje przesunięcia bitowego w prawo o jeden bit, a wynik odejmuje od „magicznej” wartości 0x5f3759df. Jest to pierwsze przybliżenie odwrotności pierwiastka kwadratowego z argumentu. Interpretując ponownie reprezentację bitową jako liczbę zmiennoprzecinkową, stosuje jedną iterację metody Newtona do wyznaczenia dokładniejszego przybliżenia. Ten algorytm oblicza przybliżenie odwrotności pierwiastka kwadratowego z liczby zmiennoprzecinkowej około cztery razy szybciej niż dzielenie zmiennoprzecinkowe.
Pierwotnie algorytm ten został przypisany Johnowi Carmackowi, lecz badania wykazały, że ten kod ma głębsze korzenie, zarówno w sprzęcie, jak i po stronie oprogramowania grafiki komputerowej. Korekty i zmiany wprowadziły tak Silicon Graphics, jak i 3dfx Interactive, w tym samym czasie, co najwcześniej znane zastosowanie implementacji Gary’ego Tarolliego dla SGI Indigo. Nie wiadomo, jak początkowo została wyznaczona stała, lecz badania rzucają pewne światło na tę kwestię.