Matematyka
(05. 12. 2006)
Jak szybko obliczyć 1/√x z liczby zmiennoprzecinkowej?
Programiści Quake'a III poradzili sobie tak:
float InvSqrt (float x){
float xhalf = 0.5f*x;
int i = *(int*)&x;
i = 0x5f3759df - (i>>1);
x = *(float*)&i;
x = x*(1.5f - xhalf*x*x);
return x;
}
Jest to nieznanego autorstwa cudo wykorzystujące jeden krok aproksymacji metodą Newtona oraz pierwsze przybliżenie pierwiastka przez podzielenie wykładnika przez dwa za pomoca przesunięcia bitowego (!) - polecam poczytanie opisu działania. Robi wrażenie. Powiedziałbym, że dziś już nikt takiego kodu nie pisze, ale nie powiem bo dawno nie widziałem na oczy nieswojego autorstwa kodu w C.
Podesłane przez Pornela.
(komentarzy: 10, ostatni: 22. 06. 2007 - 10:56:24 - ludqdfcrpq)
Skomentuj
Wyswietlen: 3069, komentarzy: 10 Feed z komentarzami
Imię: www.horacy.art.pl (06. 12. 2006 - 01:29:57)
Treść:
Srooooogie... I po takich wlasnie c kodach wiem, ze nigdy nie bede programista :)
Imię: silverrobert (06. 12. 2006 - 21:43:22)
Treść:
O ile wykorzystanie aproksymacji Newtonowskiej to zadna nowosc o tyle sposob dojscia do punktu startowego do pierwszej iteracji zwala z nog. Kuwa, moglem isc na matme, bylbym lepszym programista :/
Imię: GDR! (06. 12. 2006 - 23:11:46)
Treść:
Czy ja wiem, z matmy to tutaj akurat metoda Newtona tylko wykracza poza szkołę średnią. A ta zwalająca z nóg część wykorzystuje właściwości potęg i zapis liczb zmiennoprzecinkowych - pierwsze było na maturze, drugie - raczej wiadomo :)
Imię: silverrobert (07. 12. 2006 - 09:26:57)
Treść:
No tak ale metoda Newtona to otwierasz podrecznik z metod numerycznych prof. Oresta Popova i masz opisana jak na dloni tylko podstawiasz do wzoru a z tych wlasciwosci liczb zmiennop. trzeba wykonac 3 strony obliczen zeby dojsc do tego wyniku :|
Imię: GDR! (07. 12. 2006 - 12:57:07)
Treść:
No tak, ale nadal nie wiem gdzie w tym studia matematyczne miałyby pomóc.
To kiedy kupujemy flaszkę i rozpisujemy to odejmowanie na system binarny? :)
Imię: silverrobert (07. 12. 2006 - 18:14:02)
Treść:
Bo bez tego dojscia do wypasionej wartosci poczatkowej mamy w tym momencie calkiem zwyczajnie napisana aproksymacje Newtonem ktora wcale nie bedzie szybsza jak trza wykonac kilka iteracji. Funkcja jest piekna bo dzieki pierwszemu przyblizeniu juz po pierwszym starciu z Newtonem uzyskujemy bardzo ladny wynik o pomijalnym bledzie. Ale do tego zeby ja tak na wstepie wyprowadzic potrzebny jest doktor z matmy (ja nie chleje ostatnio :/ moze po Nowym Roku znowu zaczne to mozemy rozpisac)
Imię: GDR! (07. 12. 2006 - 18:21:59)
Treść:
No nie trzeba do tego doktora z matmy, man! Wiem dzieki czemu jest piekna, nie musisz mi mowic :P
Swietnym pomyslem jest uzycie przesuniecia bitowego, masz to ladnie wyprowadzone w tym drugim tekscie po angielsku, ale jest proste w dzialaniu. To co mnie rozbilo to uzycie odejmowania, ale watpie czy tu tez doktorat potrzebny ;) Bardziej jakis "common sense".
Imię: silverrobert (07. 12. 2006 - 19:08:29)
Treść:
Pewnie ze nie trzeba doktora z matmy jak juz masz gotowa funkcje i jedyne co pozostaje do zrobienia to napisanie krotkiego haiku na jej czesc. Samo wymyslenie takiej liczby jak 0x5f3759df to jest ciezka sprawa. Jezeli uwazasz ze podzielenie liczby przez 2 za pomoca przesuniecia bitowego czy odjecie jej od innej to wieksze osiagniecie niz znalezienie takiej liczby dla ktorej zachodzi w/w wlasciwosc to sorry ale nie dziw sie potem ze ktos sie smieje z programistow Pythona ;)
Imię: ovyptjpakj (16. 03. 2007 - 21:22:04)
Treść:
Hi! Very nice site! Thanks you very much! oeehbeogvxc
Imię: ludqdfcrpq (22. 06. 2007 - 10:56:17)
Treść:
Hello! Good Site! Thanks you! lcngiiqoztmg
