b'\n_START_ARTICLE_\nSzybka odwrotno\xc5\x9b\xc4\x87 pierwiastka kwadratowego\n_START_PARAGRAPH_\nSzybka odwrotno\xc5\x9b\xc4\x87 pierwiastka kwadratowego, czasami okre\xc5\x9blana jako szybki InvSqrt() lub przez sta\xc5\x82\xc4\x85 szesnastkow\xc4\x85 0x5f3759df \xe2\x80\x93 metoda obliczania  odwrotno\xc5\x9bci pierwiastka kwadratowego z 32-bitowej liczby zmiennoprzecinkowej w standardzie IEEE 754. Algorytm zosta\xc5\x82 prawdopodobnie opracowany w Silicon Graphics na pocz\xc4\x85tku lat 90. XX wieku, a implementacja pojawi\xc5\x82a si\xc4\x99 w 1999 roku w kodzie \xc5\xbar\xc3\xb3d\xc5\x82owym gry Quake III: Arena, lecz metoda nie pojawi\xc5\x82a si\xc4\x99 na forach publicznych, takich jak Usenet a\xc5\xbc do roku 2002 lub 2003. W \xc3\xb3wczesnym czasie podstawowa zaleta algorytmu polega\xc5\x82a na unikaniu kosztownych obliczeniowo operacji zmiennoprzecinkowych na korzy\xc5\x9b\xc4\x87 operacji na liczbach ca\xc5\x82kowitych. Odwrotno\xc5\x9bci pierwiastk\xc3\xb3w kwadratowych s\xc4\x85 u\xc5\xbcywane do obliczania k\xc4\x85t\xc3\xb3w padania i odbicia dla o\xc5\x9bwietlenia i cieniowania w grafice komputerowej._NEWLINE_Algorytm na wej\xc5\x9bciu przyjmuje dodatni\xc4\x85 32-bitow\xc4\x85 liczb\xc4\x99 zmiennoprzecinkow\xc4\x85 i zachowuje jej po\xc5\x82ow\xc4\x99 do p\xc3\xb3\xc5\xbaniejszego wykorzystania. Nast\xc4\x99pnie, interpretuj\xc4\x85c bitow\xc4\x85 reprezentacj\xc4\x99 liczby zmiennoprzecinkowej jako 32-bitow\xc4\x85 liczb\xc4\x99 ca\xc5\x82kowit\xc4\x85, dokonuje przesuni\xc4\x99cia bitowego w prawo o jeden bit, a wynik odejmuje od \xe2\x80\x9emagicznej\xe2\x80\x9d warto\xc5\x9bci 0x5f3759df. Jest to pierwsze przybli\xc5\xbcenie odwrotno\xc5\x9bci pierwiastka kwadratowego z argumentu. Interpretuj\xc4\x85c ponownie reprezentacj\xc4\x99 bitow\xc4\x85 jako liczb\xc4\x99 zmiennoprzecinkow\xc4\x85, stosuje jedn\xc4\x85 iteracj\xc4\x99 metody Newtona do wyznaczenia dok\xc5\x82adniejszego przybli\xc5\xbcenia. Ten algorytm oblicza przybli\xc5\xbcenie odwrotno\xc5\x9bci pierwiastka kwadratowego z liczby zmiennoprzecinkowej oko\xc5\x82o cztery razy szybciej ni\xc5\xbc dzielenie zmiennoprzecinkowe._NEWLINE_Pierwotnie algorytm ten zosta\xc5\x82 przypisany Johnowi Carmackowi, lecz badania wykaza\xc5\x82y, \xc5\xbce ten kod ma g\xc5\x82\xc4\x99bsze korzenie, zar\xc3\xb3wno w sprz\xc4\x99cie, jak i po stronie oprogramowania grafiki komputerowej. Korekty i zmiany wprowadzi\xc5\x82y tak Silicon Graphics, jak i 3dfx Interactive, w tym samym czasie, co najwcze\xc5\x9bniej znane zastosowanie implementacji Gary\xe2\x80\x99ego Tarolliego dla SGI Indigo. Nie wiadomo, jak pocz\xc4\x85tkowo zosta\xc5\x82a wyznaczona sta\xc5\x82a, lecz badania rzucaj\xc4\x85 pewne \xc5\x9bwiat\xc5\x82o na t\xc4\x99 kwesti\xc4\x99.\n_START_SECTION_\nPrzegl\xc4\x85d kodu\n_START_PARAGRAPH_\nPoni\xc5\xbcszy kod zawiera implementacj\xc4\x99 szybkiej odwrotno\xc5\x9bci pierwiastka kwadratowego z Quake III: Arena, z pomini\xc4\x99ciem dyrektyw preprocesora C, lecz zawieraj\xc4\x85cym oryginalne komentarze:_NEWLINE_float Q_rsqrt( float number ){_NEWLINE_        long i;_NEWLINE_        float x2, y;_NEWLINE_        const float threehalfs = 1.5F;_NEWLINE__NEWLINE_        x2 = number * 0.5F;_NEWLINE_        y  = number;_NEWLINE_        i  = * ( long * ) &y;                       // evil floating point bit level hacking_NEWLINE_        i  = 0x5f3759df - ( i >> 1 );               // what the fuck?_NEWLINE_        y  = * ( float * ) &i;_NEWLINE_        y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration//      y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed_NEWLINE__NEWLINE_        return y;}_NEWLINE_W celu wyznaczenia odwrotno\xc5\x9bci pierwiastka kwadratowego w oprogramowaniu zastosowano przybli\xc5\xbcenie dla  a nast\xc4\x99pnie przy pomocy pewnej metody numerycznej sprawdzano czy uzyskane przybli\xc5\xbcenie mie\xc5\x9bci si\xc4\x99 w dopuszczalnym zakresie b\xc5\x82\xc4\x99du wzgl\xc4\x99dem rzeczywistego wyniku. Powszechnie stosowane metody numeryczne z pocz\xc4\x85tku lat 90. XX wieku pierwsze przybli\xc5\xbcenie odczytywa\xc5\x82y z tabeli. Ten fragment kodu okaza\xc5\x82 si\xc4\x99 szybszy ni\xc5\xbc tablicowanie i oko\xc5\x82o cztery razy szybszy ni\xc5\xbc zwyczajne dzielenie zmiennoprzecinkowe. Wyst\xc4\x99puje pewna utrata dok\xc5\x82adno\xc5\x9bci, lecz jest ona rekompensowana znacz\xc4\x85cym wzrostem wydajno\xc5\x9bci. Algorytm zosta\xc5\x82 zaprojektowany dla 32-bitowej specyfikacji liczb zmiennoprzecinkowych standardu IEEE 754, lecz Chris Lemont, a p\xc3\xb3\xc5\xbaniej Charles McEniry, wykazali w swoich badaniach, \xc5\xbce podobne implementacje mo\xc5\xbcna uzyska\xc4\x87 dla innych reprezentacji zmiennoprzecinkowych._NEWLINE_Korzy\xc5\x9bci w pr\xc4\x99dko\xc5\x9bci oferowane przez szybk\xc4\x85 odwrotno\xc5\x9b\xc4\x87 pierwiastka kwadratowego pochodz\xc4\x85 od interpretowania s\xc5\x82owa rozmiaru long zawieraj\xc4\x85cego liczb\xc4\x99 zmiennoprzecinkow\xc4\x85 jako liczb\xc4\x99 ca\xc5\x82kowit\xc4\x85, a nast\xc4\x99pnie odj\xc4\x99cie jej od okre\xc5\x9blonej sta\xc5\x82ej, 0x5f3759df. Dla osoby przegl\xc4\x85daj\xc4\x85cej kod nie jest od razu jasne jaki jest cel wprowadzenia tej sta\xc5\x82ej, tak wi\xc4\x99c, jak wiele podobnych sta\xc5\x82ych w kodzie, nazywa si\xc4\x99 j\xc4\x85 \xe2\x80\x9eliczb\xc4\x85 magiczn\xc4\x85\xe2\x80\x9d. To ca\xc5\x82kowitoliczbowe odejmowanie i przesuni\xc4\x99cie bitowe zwraca s\xc5\x82owo, kt\xc3\xb3re zinterpretowane jako liczba zmiennoprzecinkowa jest przybli\xc5\xbceniem odwrotno\xc5\x9bci pierwiastka kwadratowego argumentu funkcji. Po wykonaniu jednej iteracji metod\xc4\x85 Newtona wymagana dok\xc5\x82adno\xc5\x9b\xc4\x87 jest osi\xc4\x85gni\xc4\x99ta a kod zako\xc5\x84czony. Ten algorytm zwraca wyniki o rozs\xc4\x85dnej dok\xc5\x82adno\xc5\x9bci, wykorzystuj\xc4\x85c unikatowe pierwsze przybli\xc5\xbcenie dla metody Newtona, chocia\xc5\xbc jest znacznie wolniejszy i mniej dok\xc5\x82adny ni\xc5\xbc instrukcja SSE rsqrtss na procesorach x86, wydanych tak\xc5\xbce w 1999 roku.\n_START_SECTION_\nPrzyk\xc5\x82ad dzia\xc5\x82ania\n_START_PARAGRAPH_\nRozwa\xc5\xbcmy przyk\xc5\x82ad z liczb\xc4\x85  dla kt\xc3\xb3rej chcemy wyznaczy\xc4\x87 wielko\xc5\x9b\xc4\x87  Pierwsze kroki algorytmu wygl\xc4\x85daj\xc4\x85 nast\xc4\x99puj\xc4\x85co:_NEWLINE_00111110001000000000000000000000 Bitowy wz\xc3\xb3r x lub i_NEWLINE_00011111000100000000000000000000 Przesuni\xc4\x99cie w prawo o jedn\xc4\x85 pozycj\xc4\x99: (i >> 1)_NEWLINE_01011111001101110101100111011111 Magiczna sta\xc5\x82a 0x5f3759df_NEWLINE_01000000001001110101100111011111 Wynik oblicze\xc5\x84 0x5f3759df \xe2\x80\x93 (i >> 1)_NEWLINE_Interpretacja ostatniego wzoru bitowego jako liczby zmiennoprzecinkowej daje przybli\xc5\xbcenie  kt\xc3\xb3re r\xc3\xb3\xc5\xbcni si\xc4\x99 od dok\xc5\x82adnego wyniku 0 3,4%. Po jednej iteracji metod\xc4\x85 Newtona ostateczny wynik wynosi  z uchybem tylko 0,17%.\n_START_SECTION_\nDok\xc5\x82adno\xc5\x9b\xc4\x87\n_START_PARAGRAPH_\nJak jest to przedstawione wy\xc5\xbcej, przybli\xc5\xbcenie jest zaskakuj\xc4\x85co dok\xc5\x82adne. Wykres po prawej przedstawia funkcj\xc4\x99 b\xc5\x82\xc4\x99du (tj. b\xc5\x82\xc4\x99du po ulepszeniu wyniku dzi\xc4\x99ki wykonaniu jednej iteracji metody Newtona), dla warto\xc5\x9bci rozpoczynaj\xc4\x85cych si\xc4\x99 od 0,01, w kt\xc3\xb3rej biblioteka standardowa zwraca 10,0 jako wynik, podczas gdy InvSqrt() zwraca 9,982522, r\xc3\xb3\xc5\xbcni\xc4\x85c si\xc4\x99 o 0,017479, czyli 0,175%. Jest to najwi\xc4\x99kszy b\xc5\x82\xc4\x85d bezwzgl\xc4\x99dny, kt\xc3\xb3ry maleje dla rosn\xc4\x85cych argument\xc3\xb3w, natomiast b\xc5\x82\xc4\x85d wzgl\xc4\x99dny pozostaje w tych samych granicach dla wszystkich rz\xc4\x99d\xc3\xb3w wielko\xc5\x9bci.\n_START_SECTION_\nHistoria i badania\n_START_PARAGRAPH_\nKod \xc5\xbar\xc3\xb3d\xc5\x82owy Quake III nie by\xc5\x82 upubliczniony a\xc5\xbc do QuakeCon 2005, lecz kopie kodu szybkiej odwrotno\xc5\x9bci pierwiastka kwadratowego pojawi\xc5\x82y si\xc4\x99 na Usenet i innych forach ju\xc5\xbc w 2002 lub 2003 roku. Pocz\xc4\x85tkowe spekulacje wskazywa\xc5\x82y na Johna Carmacka jako prawdopodobnego autora kodu, lecz on zaprzeczy\xc5\x82 i zasugerowa\xc5\x82, \xc5\xbce ten kod napisa\xc5\x82 Terje Mathisen, utalentowany programista asemblerowy, kt\xc3\xb3ry wcze\xc5\x9bniej pomaga\xc5\x82 id Software przy optymalizacji Quake\xe2\x80\x99a. Mathisen napisa\xc5\x82 implementacj\xc4\x99 podobnego kodu bitowego w p\xc3\xb3\xc5\xbanych latach 90. XX wieku, lecz okaza\xc5\x82o si\xc4\x99, \xc5\xbce w historii grafiki komputerowej 3D pierwsi autorzy pojawili si\xc4\x99 znacznie wcze\xc5\x9bniej. Najwcze\xc5\x9bniejsz\xc4\x85 znan\xc4\x85 i u\xc5\xbcywan\xc4\x85 implementacj\xc4\x99 napisa\xc5\x82 Gary Tarolli dla SGI Indigo. Rys Sommefeldt stwierdzi\xc5\x82, \xc5\xbce algorytm zosta\xc5\x82 opracowany przez Grega Walsha w Ardent Computer w porozumieniu z Clevem Molerem, tw\xc3\xb3rc\xc4\x85 programu MATLAB, chocia\xc5\xbc ostateczny dow\xc3\xb3d autorstwa nie istnieje._NEWLINE_Nie wiadomo dok\xc5\x82adnie w jaki spos\xc3\xb3b wyznaczono warto\xc5\x9b\xc4\x87 magicznej sta\xc5\x82ej. Chris Lomont opracowa\xc5\x82 funkcj\xc4\x99 do minimalizacji b\xc5\x82\xc4\x99du przybli\xc5\xbcenia przez wyb\xc3\xb3r magicznej liczby R z przedzia\xc5\x82u. Najpierw wyznaczy\xc5\x82 optymaln\xc4\x85 sta\xc5\x82\xc4\x85 dla etapu liniowej aproksymacji jako 0x5f37642f, blisko 0x5f3759df, lecz ta nowa sta\xc5\x82a dawa\xc5\x82a odrobin\xc4\x99 mniej dok\xc5\x82adne wyniki po wykonaniu jednej iteracji metod\xc4\x85 Newtona. Nast\xc4\x99pnie Lomont poszukiwa\xc5\x82 optymalnej sta\xc5\x82ej nawet po jednej i dw\xc3\xb3ch iteracjach metody Newtona, i znalaz\xc5\x82 0x5f375a86, kt\xc3\xb3ra jest bardziej dok\xc5\x82adna ni\xc5\xbc oryginalna dla ka\xc5\xbcdej iteracji. Stwierdzi\xc5\x82, pytaj\xc4\x85c, czy dok\xc5\x82adna warto\xc5\x9b\xc4\x87 sta\xc5\x82ej zosta\xc5\x82a wybrana przez jej wyprowadzenie czy metod\xc4\x85 pr\xc3\xb3b i b\xc5\x82\xc4\x99d\xc3\xb3w. Lomont wskaza\xc5\x82, \xc5\xbce \xe2\x80\x9emagiczna liczba\xe2\x80\x9d dla 64-bitowej wersji liczby zmiennoprzecinkowej IEEE\xc2\xa0754 (podw\xc3\xb3jna precyzja) to 0x5fe6ec85e7de30da, lecz w rzeczywisto\xc5\x9bci okaza\xc5\x82o si\xc4\x99, \xc5\xbce to 0x5fe6eb50c7b537a9. Charles McEniry wykona\xc5\x82 podobne, lecz bardziej wyrafinowane optymalizacje wobec prawdopodobnych warto\xc5\x9bci R. Jego pocz\xc4\x85tkowa szukaj\xc4\x85ca metoda czo\xc5\x82gowa zwr\xc3\xb3ci\xc5\x82a t\xc4\x99 sam\xc4\x85 warto\xc5\x9b\xc4\x87 jak\xc4\x85 wyznaczy\xc5\x82 Lomont. Kiedy pr\xc3\xb3bowa\xc5\x82 znale\xc5\xba\xc4\x87 sta\xc5\x82\xc4\x85 metod\xc4\x85 r\xc3\xb3wnego podzia\xc5\x82u, uzyska\xc5\x82 specyficzn\xc4\x85 warto\xc5\x9b\xc4\x87 R, kt\xc3\xb3ra wyst\xc4\x99puje w funkcji. Utwierdzi\xc5\x82o to go w przekonaniu, \xc5\xbce sta\xc5\x82a mog\xc5\x82a by\xc4\x87 oryginalnie wyprowadzona \xe2\x80\x9emetod\xc4\x85 r\xc3\xb3wnego podzia\xc5\x82u do zadanej dok\xc5\x82adno\xc5\x9bci\xe2\x80\x9d.'