Czy komputer potrafi liczyć?

Co będzie, gdy powiem Wam, że komputer nie zawsze zwraca poprawny wynik działań arytmetycznych? I wcale nie chodzi tutaj o skomplikowane obliczenia! Okazuje się, że nasz blaszany przyjaciel ma problemy nawet z trywialnymi operacjami arytmetycznymi. Wszak każdy potrafi powiedzieć ile wynosi wynik takiego działania jak 1000.1 - 1000. Niewiele zmieni, jeśli zamiast 1000, sto razy odejmę 10 (bo 10*100 = 1000). Tylko czy oby na pewno? Sprawdźmy to na prościutkim programie:

[code=c++] float x = 1000.1; int i; for(i=0;i<100;i++){ x = x‑10; } std::cout<

Kompilujemy i... wynik jest niepoprawny

Sprawdzamy kod jeszcze raz - wszystko wydaje się ok.

Więc w czym problem?

Problemem okazuje się być sposób, w jaki zapisywane są liczby w naszych komputerach. To, oraz komplikacje które z tego wynikają. Nie mam zamiaru tutaj tego opisywać, bo nie widzę sensu w przepisywaniu wikipedii, gdzie jest to dość ładnie opisane. Zresztą większość osób czytających ten wpis zapewne ma o tym pojęcie, możliwe jednak że nie zdają sobie sprawy z tego, jak bardzo może to zakłamywać wyniki prostych operacji, jak ta wyżej. Przypomnę tylko w skrócie, że na skończonej liczbie bitów nie da się zapisać każdej liczby (tak jak na skończonej liczbie cyfr dziesiętnych nie da się zapisać każdej liczby, przykładowo 1/3). W systemie binarnym mamy problem nawet z taką liczbą jak 1/10 ! Przez to podczas wykonywania obliczeń otrzymujemy wyniki z błędem, zwłaszcza przy odejmowaniu bliskich sobie liczb (jeśli znajdzie się grono odbiorców mogę pokusić się o opisanie tego dokładniej - dzisiaj pokażę jedynie kilka ciekawych błędów). Przeważnie błędy te są na tyle małe, że ich nie zauważamy, ale jak widać przy stukrotnym powieleniu operacji błędy się kumulują dając już zauważalne odchylenie. Okazuje się, że może być o wiele gorzej. Albo dziwniej...

[code=c++] float x = 1.0; while(1!=x+1){ x = x/2; } if(x!=0){ std::cout<<"Komputer twierdzi ze x jest rozne od 0"<

Kolejność dodawania?

Było wielokrotne odejmowanie, pobawmy się zatem dodawaniem :) Pytanie brzmi: czy oby na pewno kolejność dodawania nie ma znaczenia? Zobaczmy to na przykładzie:

[code=C++]float s1, s2; int i, j; s1 = 0.0; s2 = 0.0; for(i=1; i<=100000; i++){ s1 = s1 + 1.0/(float)(i*(i+1)); } for(j=100000; j>=1; j-‑){ s2 = s2 + 1.0/(float)(j*(j+1)); } std::cout<

Niby nic złego się nie powinno stać, ale zerknijmy na wyniki:

I co w związku z tym?! Przecież to malutkie błędy!

Błędy są malutkie, bo przykłady nie należą do zbyt wyrafinowanych. Nie oznacza to, że błędy numerycznie nie mogą być katastroficzne w skutkach. Przykładem może być tutaj eksplozja rakiety wartej 500 milionów dolarów Ariane 5. Przyczyna? Błąd konwersji liczby zmiennoprzecinkowej (64 bity) na całkowitą (16 bitów) i rzucenie wyjątku przez system. Głupia rzecz? Jak widać nie. Drugim przykładem może być system PATRIOT który w 1991 roku zawiódł, co kosztowało życie 28 amerykańskich żołnierzy. Gdy zegar baterii (trzymany jako liczba całkowita) osiągał duże wielkości, przy konwersji na liczbę zmiennoprzecinkową powodowało spory błąd. Pewnego dnia system działał od 100 godzin pociągając za sobą błąd 1/3 sekundy. To natomiast przełożyło się na uderzenie 700 metrów od pierwotnego celu! Można było tego uniknąć, bo aby system działał poprawnie wystarczyło restartować go co kilka godzin. Co ciekawe, Amerykanie wiedzieli o luce, a aktualizacja była w drodze - niczym w (amerykańskim) dramacie hollywoodzkim dotarła dzień za późno.

Wpis zainspirowany oraz oparty jest w dużej mierze na wykładzie dr Pawła Woźnego, dotyczącego analizy numerycznej.