{"id":1017,"date":"2016-10-12T20:00:14","date_gmt":"2016-10-12T18:00:14","guid":{"rendered":"http:\/\/morony.pl\/?p=1017"},"modified":"2016-10-12T00:35:23","modified_gmt":"2016-10-11T22:35:23","slug":"czego-nie-wiemy-o-liczbach-zmiennoprzecinkowych","status":"publish","type":"post","link":"https:\/\/morony.pl\/?p=1017","title":{"rendered":"Czego nie wiemy o liczbach zmiennoprzecinkowych"},"content":{"rendered":"

Przez ostatnie 4 lata prowadzi\u0142em na Wydziale Fizyki \u0107wiczenie do kilku kurs\u00f3w programowania w pythonie i c++. Kilka razy spotka\u0142em si\u0119 z pytaniem o liczby zmiennoprzecinkowe. Poruszamy na zaj\u0119ciach kwesti\u0119 zapisu binarnego liczb ca\u0142kowitych i wtedy pojawia si\u0119 pytanie o liczby rzeczywiste. Do tej pory odpowiada\u0142em bardzo skr\u00f3towo, \u017ce “jest to skomplakowne”, bardzo sprytne, ale nie pozbawione wad. W przypadku liczb ca\u0142kowitych sprawa jest prosta. W danej ilo\u015bci bit\u00f3w mo\u017cemy przechowa\u0107 dany zakres liczb ca\u0142kowitych. Z liczbami zmiennoprzecinkowymi problem polega na tym, \u017ce w ka\u017cdym przedziale jest ich niesko\u0144czenie wiele, a my mamy tylko 32 albo 64 bity. Wi\u0119c jak to w\u0142a\u015bciwie jest? O samej formie zapisu mo\u017cna oczywi\u015bcie przeczyta\u0107 wszystko w Wikipedii – ja chc\u0119 zrobi\u0107 eksperyment. Na pierwszy ogie\u0144 liczby typu float, czyli 32 bitowe (1 bit na znak, 8 bit\u00f3w na wyk\u0142adnik i 23 na mantys\u0119). 32 bity daje jakie\u015b 4\u00a0294\u00a0967\u00a0296 kombinacji – to na tyle ma\u0142o, \u017ce mog\u0119 sprawdzi\u0107 wszystkie. W ramach testu sprawdzam ile liczb mie\u015bci si\u0119 w 4 przedzia\u0142ach: 0-1, 1-2, 1000-1001 i 1000000-1000001:<\/p>\n

int main()\r\n{\r\n\tfloat f;\r\n\tuint i;\t \r\n\tstd::vector range = {0, 1, 1000, 1000000};\r\n\tstd::vector count = {0, 0, 0, 0};\r\n\tfor(i = 0; i=range[a] && f < range[a]+1)\r\n\t\t\t\tcount[a]++;\r\n\t\t}\r\n\t}\r\n\tfor(int a = 0; a < range.size(); a++)\r\n\t{\r\n\t\tstd::cout << range[a] << \"-\" << range[a]+1 << \":\\t\" << count[a] << std::endl;\r\n\t}\r\n}\r\n<\/pre>\n
Wynik mamy po nieca\u0142ych 2 minutach. Policzone ilo\u015bci liczb s\u0105 bardzo ciekawe:
\n
\"screenshot_33\"<\/a> <\/center>
\nOd razu wida\u0107 kilka zale\u017cno\u015bci. W zakresie od 1 do 2 jest dok\u0142adnie 2^23 liczb - tak jakby by\u0142y to wszystkie \"mantysy\" dla jednego wyk\u0142adnika. W zakresie od 0 do 1 jest dok\u0142adnie 2^23*(2^7-1)-1 - czyli wszystkie mantysy dla po\u0142owy wyk\u0142adnik\u00f3w (bez jednego). Im wi\u0119ksza liczba tym mniejsza dok\u0142adno\u015b\u0107 - mamy do dyspozycji 2^31 a musimy m\u00f3c pokaza\u0107 zar\u00f3wno bardzo ma\u0142e liczby i te gigantyczne. <\/p>\n
Z liczbami w pojedynczej precyzji sprawa by\u0142a prosta - uda\u0142o si\u0119 sprawdzi\u0107 wszystkie kombinacje w nieca\u0142e 2 minuty. Przy podw\u00f3jnej precyzji mamy 64 bity, wi\u0119c sprawdzenie wszystkich zaj\u0119\u0142oby 16000 lat. Szkoda czasu. Mo\u017cemy natomiast pobawi\u0107 si\u0119 takim kodem:<\/p>\n
int main()\r\n{\r\n\tunion\r\n\t{\r\n\t\tuint64_t input;\r\n\t\tuint64_t   output;\r\n\t} data;\r\n\r\n\tuint64_t x = 5;\r\n\tdata.input = x;\r\n\tstd::bitset   bits(data.output);\r\n\r\n\tfor(uint64_t a = 0; a<=2048; a++)\r\n\t{\r\n\t\tfor(uint64_t b = 0; b<=pow(2,52)-1; b+=pow(2,52)-1)\r\n\t\t{\r\n\t\t\tx = b+(a<<52);\r\n\t\t\tdata.input = x;\r\n\t\t\tbits = data.output;\r\n\t\t\tdouble f;\r\n\t\t\tmemcpy(&f, &x, sizeof(f));\r\n\t\t\tstd::cout << std::setw(4)<< a<< '\\t'<< std::setw(16)<<  b << '\\t'<< std::setw(12) << f << '\\t' << bits  << std::endl;\r\n\t\t}\r\n\t\tstd::cout << std::endl;\r\n\t}\r\n}\r\n<\/pre>\n
Powy\u017cszy kod wypisze zakres liczb dla ka\u017cdego z 2^11 wyk\u0142adnik\u00f3w. Mantysa ma 52 bity (~4.5*10^15), wi\u0119c od 1 do 2 mamy w\u0142a\u015bnie 2^52 liczb, Tyle samo od 2 do 4, 4 do 8 itd:<\/p>\n
\"screenshot_34\"<\/a><\/center><\/p>\n
Na powy\u017cszym przyk\u0142adzie pierwsza kolumna to wyk\u0142adnik, druga to mantysa, trzecia to warto\u015b\u0107 liczby, a czwarta to reprezentacja binarna. <\/p>\n
Nie chc\u0119 tutaj wnika\u0107 w szczeg\u00f3\u0142y samego formatu. Zale\u017cy mi na pokazaniu specyfiki takiego pami\u0119tania liczb. Mo\u017cecie modyfikowa\u0107 i uruchamia\u0107 powy\u017csze kody, a dowiecie si\u0119 wi\u0119cej o liczbach zmiennoprzecinkowych. Dodatkowo powy\u017csze przyk\u0142ady powinny dobrze obrazowa\u0107 kolosaln\u0105 r\u00f3\u017cnic\u0119 pomi\u0119dzy pojedyncz\u0105 i podw\u00f3jn\u0105 precyzj\u0105. <\/p>\n
Musimy pami\u0119ta\u0107, \u017ce operuj\u0105c na bardzo du\u017cych liczbach, gdzie dok\u0142adno\u015b\u0107 zapisu zmiennoprzecinkowego jest ma\u0142a, mo\u017cemy wprowadza\u0107 b\u0142\u0119dy numeryczne - w szczeg\u00f3lno\u015bci gdy \u0142\u0105czymy wielkie i ma\u0142e liczby. <\/p>\n
Kto dowiedzia\u0142 si\u0119 czego\u015b nowego klika \u0142apk\u0119 w g\u00f3r\u0119!<\/p>\n","protected":false},"excerpt":{"rendered":"
Przez ostatnie 4 lata prowadzi\u0142em na Wydziale Fizyki \u0107wiczenie do kilku kurs\u00f3w programowania w pythonie i c++. Kilka razy spotka\u0142em si\u0119 z pytaniem o liczby zmiennoprzecinkowe. Poruszamy na zaj\u0119ciach kwesti\u0119 zapisu binarnego liczb ca\u0142kowitych i wtedy pojawia si\u0119 pytanie o liczby rzeczywiste. Do tej pory odpowiada\u0142em bardzo skr\u00f3towo, \u017ce “jest to skomplakowne”, bardzo sprytne, ale […]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/morony.pl\/index.php?rest_route=\/wp\/v2\/posts\/1017"}],"collection":[{"href":"https:\/\/morony.pl\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/morony.pl\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/morony.pl\/index.php?rest_route=\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/morony.pl\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1017"}],"version-history":[{"count":10,"href":"https:\/\/morony.pl\/index.php?rest_route=\/wp\/v2\/posts\/1017\/revisions"}],"predecessor-version":[{"id":1029,"href":"https:\/\/morony.pl\/index.php?rest_route=\/wp\/v2\/posts\/1017\/revisions\/1029"}],"wp:attachment":[{"href":"https:\/\/morony.pl\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1017"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/morony.pl\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1017"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/morony.pl\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1017"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}