Niekończące się liczby

Nieskończoność jest jednym z tych pojęć matematycznych, które z samej natury nie dają się odnieść do codziennego życia. W informatyce chyba najbliższym do niej odniesieniem jest nieskończona pętla – czyli taka, której warunek stopu nigdy nie będzie prawdziwy. Wiadomo jednak, że w rzeczywistości ową pętlę prędzej czy później przerwie jeśli nie debugujący kod programista, to jakiekolwiek inne zdarzenie z gatunku losowych, z brakiem prądu włącznie.
Dlatego też intuicyjne pojmowanie tego pojęcia często bywa nieadekwatne do jego faktycznego, matematycznego znaczenia. Można się było o tym przekonać niedawno za sprawą pewnego wątku na forum Warsztatu.

Dotyczył on pewnego matematycznego faktu – iż liczba 0,(9) równa się po prostu 1. Zapis 0,(9) oznacza tutaj – zgodnie z przyjętą powszechnie konwencją – ciąg 0,999… nieskończonej liczby dziewiątek w rozwinięciu dziesiętnym liczby.
Powyższa równość bywa często kwestionowana przez osoby niezbyt dobrze zaznajomione z bardziej abstrakcyjnymi koncepcjami matematycznymi, jak chociażby granice, szeregi czy własności zbioru liczb rzeczywistych. “Intuicyjnie” – aczkolwiek zupełnie błędnie – może się wydawać, że 0,(9) nie jest równe jeden, a jest jedynie liczbą bardzo, bardzo jej bliską. Najlepiej tak bliską, że już żadnej bliższej być nie może.

To oczywiście jest kompletną bzdurą, bo taka liczba nie istnieje. Jedną z najważniejszych cech liczb rzeczywistych jest właśnie to, że:

czyli że dla dowolnych dwóch takich liczb zawsze da się znaleźć trzecią, dającą się “włożyć” między nimi. Co więcej, takich pośrednich wartości jest całkiem sporo, bo dokładnie tyle samo co w całym zbiorze – nieskończenie wiele.
I tu właśnie już wyraźnie pojawia się nieskończoność, która – jak sądzę – jest głównym “winowajcą” stwierdzeń, że jakoby . Gdy spotykamy się z nim, dość naturalną reakcją jest bowiem zapytanie, ile wobec tego wynosi różnica . Następująca dalej próba zapisania rzekomej “liczby tak bliskiej zera, że już bliższej nie ma” kończy się następnie wyprodukowaniem potworka w rodzaju 0,(0)1. W założeniu ma być on odczytywany jako liczba, która w zapisie dziesiętnym ma nieskończoną liczbę zer, po których następuje jedna jedynka…

Chwila! Jak w ogóle coś może występować na końcu nieskończonego ciągu?!… Ano właśnie – tutaj następuje efektowna logiczna sprzeczność, która ładnie dowodzi nieprawidłowości założenia (czyli nieszczęsnej równości ). Pokazuje też, że mamy tu w gruncie rzeczy do czynienia z nierozumieniem pojęcia tzw. nieskończoności potencjalnej, czyli najprostszego ujęcia idei nieskończoności: jako takiej ilości, która jest większa od każdej, dowolnie dużej skończonej liczby.
A to przecież nie wszystko, co matematyka na temat nieskończoności ma do powiedzenia. Wręcz przeciwnie – to dopiero marny wycinek, jako że teoria zbiorów przekonuje nas, że tak naprawdę rodzajów nieskończoności jest… nieskończenie wiele :) Uff, jak dobrze, że w informatyce wszystko, na czym się w praktyce operuje jest z założenia skończone i możliwe do policzenia… A jeśli nawet nie, to przecież zawsze można się ograniczyć do jakiegoś ograniczonego z góry zbioru wartości, które wspieramy. Tak jak pewien protokół używany do routowania, dla którego nieskończoną liczbą jest już… 16 :]

Naprawdę duże liczby

Programując, rzadko mamy do czynienia z bardzo dużymi wartościami. Dowodem na to jest choćby fakt, że 32-bitowe systemy dopiero teraz zaczynają być w zauważalny sposób zastępowane 64-bitowymi. Jedynie w przypadku rozmiarów bardzo dużych plików operowanie zmiennymi mogącymi zmieścić wartości większe niż 4 miliardy jest konieczne.
Inne dziedziny życia i nauki przynoszą nam nieco większe wartości. Ekonomia czasami mówi o dziesiątkach bilionów (PKB dużych krajów), a fizyka często posługuje się wielkościami zapisywanymi przy pomocy notacji potęgowej – aż do ok. 10⁸⁰, czyli szacowanej liczby wszystkich atomów we Wszechświecie.

Wydawać by się mogło, że wielkość ta jest bliska górnej granicy wartości, jakich kiedykolwiek moglibyśmy używać w sensownych zastosowaniach. Okazuje się jednak, że tak nie jest; co więcej, jakakolwiek liczba zapisana za pomocą co najwyżej potęgowania jest tak naprawdę bardzo, bardzo mała.
Do zapisywania naprawdę dużych liczb potrzebne są bowiem inne notacje. Jednym z takich sposobów zapisu jest notacja strzałkowa Knutha, która jest “naturalnym” rozszerzeniem operacji algebraicznych. Tak jak dodawanie jest iterowaną inkrementacją, mnożenie jest iterowanym dodawaniem, a potęgowanie – iterowanym mnożeniem:

,

tak każdy następny operator strzałkowy jest iterowaną wersją poprzedniego. I tak pierwszy z nich, to zwykłe potęgowanie , ale już drugi:

jest odpowiednikiem wielokrotnego podnoszenia danej liczby do jej potęgi. W ogólności, skracając ciąg n strzałek do , otrzymujemy definicję:

Na pierwszy rzut oka może wydawać się to nieoczywiste, jednak już dla n = 3 i jednocyfrowych argumentów, wielkość liczb otrzymywanych przy użyciu notacji strzałkowej znacznie przekracza te, które można w wygodny sposób zapisać przy pomocy samego potęgowania. Chcąc je mimo wszystko przedstawić w tej postaci, trzeba się uciekać do sztuczek z klamerkami:

Oczywiście wraz ze wzrostem liczby strzałek nawet takie triki przestają wystarczać.

W tej chwili pewnie nasuwa się proste pytanie: czy z takiego systemu zapisu jest w ogóle jakiś pożytek, jeśli nikt nie posługuje się na poważnie tak wielkimi liczbami?… Odpowiedź jest jak najbardziej twierdząca, mimo że założenie w pytaniu jest nieprawdziwe. Otóż niektóre dziedziny matematyki używają nie tylko takich, ale i znacznie większych wartości – i nie chodzi tu nawet o teorię liczb, którą to jako pierwszą podejrzewalibyśmy o rzucanie liczbami “z kosmosu”.
Według Księgi Rekordów Guinnessa największą skończoną liczbą kiedykolwiek użytą w poważnym dowodzie matematycznym jest bowiem tzw. liczba Grahama, będącą górnym ograniczeniem pewnej wielkości występującej w problemie luźno związanym z grafami. Żeby ją zdefiniować, można użyć notacji strzałkowej – trzeba to jednak zrobić… iteracyjnie, wprowadzając pomocniczy ciąg g_n:

Już pierwszy jego wyraz nie daje się zapisać w postaci potęgowej, ale gwoździem programu jest zauważenie, że kolejne jego elementy posługują się poprzednimi w celu określenia liczby strzałek w operatorze . Innymi słowy, mamy tu wejście na kolejny poziom abstrakcji i stoimy już chyba tak wysoko, że aż strach spoglądać w dół ;)
Co jednak ze wspomnianą wcześniej liczbą Grahama? Teraz na szczęście jej określenie jest już bardzo proste. Jest ona równa ni mniej, ni więcej, jak tylko… g₆₄ :-)

W matematyce jest odwrotnie

W pewnych sprawach kiedyś występowała alternatywa dwóch równoważnych możliwości i trzeba było w końcu zdecydować się na wybór jednej z nich. Matematycy często ustalają w ten sposób coś “dla porządku” lub dla tzw. ustalenia uwagi. Jak na ironię zauważyłem jednak, że zwykle to właśnie w matematyce niektóre powszechnie obowiązujące umowy wcale nie wprowadzają porządku, gdyż są dokładnie odwrotne względem intuicji lub codziennego doświadczenia. Oto przykłady:

• Kąty w kartezjańskim układzie współrzędnych na płaszczyźnie – ze szczególnym uwzględnieniem współrzędnych biegunowych – są tak określone, że większe ich wartości oznaczają coraz większe przesunięcie w kierunku przeciwnym do ruchu wskazówek zegara.
• Tzw. główna przekątna macierzy przy jej zwykłej reprezentacji tablicowej obejmuje komórki od lewego górnego do prawego dolnego rogu. Linia, która jest pochylona w ten sposób, przypomina znak backslash :)
• 
  Ta funkcja jest wypukła :)

  Funkcje rzeczywiste nazywane wypukłymi narysowane w postaci wykresu przyjmują postać krzywej wygiętej do dołu, co sugeruje nazywać je raczej… wklęsłymi (obrazuje to rysunek po prawej).

• Tradycyjnie wektory w matematyce zapisuje się jako kolumnowe (czyli macierze ), a nie wierszowe (). To niby nic specjalnego, ale skutek “uboczny” jest taki, że macierze przekształceń (obrotu, translacji, itp.) w stosunku do takich wektorów należy aplikować w kolejności odwrotnej względem rzeczywistej kolejności transformacji, którą chcemy uzyskać (kiedyś już pisałem więcej na ten temat).

Na pewno nie są to wszystkie przypadki podobnych “niefortunnych” rozstrzygnięć; z pewnością dałoby się znaleźć ich więcej. Na pewno też każdy z nich daje się w zadowalający sposób uzasadnić (jak chociażby przekątną macierzy – jest ona po prostu definiowana przez te komórki, których numer wiersza jest równy numerowi kolumny). I paradoksalnie to właśnie jest w nich najgorsze: nie da się z nimi nic zrobić, jak tylko zwyczajnie zapamiętać :)

Płaska wizualizacja funkcji 3D

Źródło

Funkcje, których dziedziną jest podzbiór R² (czyli płaszczyzna) ciężko jest przedstawić na płaskim ekranie w sposób poglądowy, a jednocześnie pozwalający na odczytanie jakichś wartości. O ile bowiem izometryczny rzut 3D wygląda efektownie, to poza ogólnym kształtem powierzchni nie przedstawia wielkiej ilości informacji. Sprawa wygląda trochę lepiej, jeśli taką figurę możemy jeszcze obracać… co aczkolwiek może być z kolei trudne do zrealizowania np. na wydruku :]

Źródło

Jednym z wyjść może być tutaj zastosowanie sposobu używanego do map wysokości w grach. Nietrudno zauważyć, że są one niczym innym jak właśnie funkcjami typu R²->R, a reprezentowane są najczęściej jako bitmapy w odcieniach szarości: jasność piksela x,y odpowiada w nich wysokości odpowiedniego punktu terenu.
Takie heightmapy wprawdzie łatwo się rysuje, ale niespecjalnie nadają się do pokazania jako ilustracja czegokolwiek – odcienie szarości są przecież z definicji szare i nieciekawe :) Dlatego bardzo spodobał mi się prosty pomysł na uczynienie tej reprezentacji znacznie ładniejszą, o którym to usłyszałem niedawno.

Idea jest prosta: po co używać samych szarości, skoro mamy do dyspozycji całą paletę kolorów?… Każdy kolor w reprezentacji RGB jest przecież tożsamy z liczbą, co widać najbardziej, jeśli weźmiemy jego typową reprezentację 32-bitową:

W niej “największym” kolorem jest kolor biały (0x00FFFFFF, czyli 2²⁴ – 1), zaś “najmniejszym” czarny (0x0), a pomiędzy nimi włącznie występuje każdy z 256³ możliwych kolorów. Jeśli teraz przeskalujemy wartości naszej funkcji do tak określonego przedziału (lub nieco mniejszego), a następnie przekonwertujemy każdą z tych 32-(a właściwie 24-)bitowych liczb na odpowiadający jej kolor RGB, to otrzymamy w ten sposób heightmapę o znacznie bogatszej palecie barw niż poprzednio.
Jeśli ponadto używamy dokładnie takiej reprezentacji liczbowej kolorów, jak powyżej (najmłodsze bity na kolor niebieskie, a najstarsze używane na czerwony), to zauważymy, że rozkład barw w wyniku jest całkiem znajomy. I tak obszary niebieskie odpowiadają wartościom najmniejszym, zielone średnim, żółte – wysokim, a czerwone – najwyższym. Łącznie przypomina mapę hipsometryczną – czyli, jakby nie patrzył, mapę wysokości właśnie :)

Do czego może przydać się takie cudo, oprócz wspomnianej już wizualizacji funkcji R²->R na płaszczyźnie? Pewnie do niewielu rzeczy :) Ja wpadłem jednak na jeszcze jedno potencjalne zastosowanie.
Ponieważ wynikowy obrazek używa tak “geograficznych” barw, może on całkiem dobrze wyglądać jako… tło minimapy pokazywanej w grze, która rozgrywa się na terenie opisanym mapą wysokości. Oczywiście rzecz wymagałaby dopracowania: przede wszystkim bardziej starannego dobrania kolorów brzegowych (niekoniecznie białego i czarnego) oraz być może kolorów pośrednich (np. kolor poziomu morza), a i pewnie zastosowania jakichś filtrów na wynikowym obrazku (np. wygładzania). Efekty mogłyby być jednak interesujące, co widać obok.

Skąd wziąć matematyczne stałe

Jeśli tylko liczymy coś bardziej skomplikowanego niż rozmieszczenie kontrolek w oknie, to niechybnie zaczniemy potrzebować którejś ze stałych matematycznych – na przykład π. Co wtedy robimy? Ano całkiem często skutkuje to włączeniem do programu deklaracji typu:

Nie jest to oczywiście wielkie zło (a już na pewno mniejsze niż bezpośrednie korzystanie z definicji typu π = 4atan(1)), ale w większości przypadków jest to też wyważanie otwartych drzwi. Potrzebne stałe mamy bowiem często już gdzieś zdefiniowane – trzeba tylko wiedzieć, gdzie ich poszukać:

• W C/C++ mamy M_PI, M_E, a nawet M_LN10 czy M_SQRT2 zdefiniowane w math.h lub cmath. Definicje te nie są jednak częścią standardu, więc dbające o zgodność kompilatory (czyli większość kompilatorów w ogóle) wymagają pewnych #define‘ów przed dołączeniem ww. nagłówków. I tak dla Visual C++ jest to _USE_MATH_DEFINES, a dla GCC bodajże prawie dowolne z makr _SOURCE (jak _GNU_SOURCE czy _ALL_SOURCE).
• W DirectX mamy tylko DX3DX_PI i D3DX1BYPI (1/π) – co nie dziwi, bo przecież w grafice więcej do szczęścia nie potrzeba ;) Obie te stałe są zdefiniowane w d3dx#math.h (gdzie # to numer wersji DirectX), który to nagłówek jest dołączany automatycznie jeśli korzystamy z D3DX.
• W .NET mamy stałe PI i E zdefiniowane jako statyczne pola klasy System.Math. W Javie klasa java.lang.Math zawiera dwa identycznie zdefiniowane pola.

Jak zatem łatwo zauważyć, wynajdywanie koła w postaci definicji π czy e jest w wielu przypadkach nieuzasadnione :]

Dwa paradoksy prawdopodobieństwa

Na dzisiaj przewidziałem ciekawostki z nieco innej niż zwykle beczki :) Chciałem mianowicie pokazać dwa przykłady na to, jak intuicyjnie całkiem proste pojęcie matematyczne w rzeczywistości jest bardzo podatne na niewłaściwe zrozumienie. Chodzi tutaj o zwykłe prawdopodobieństwo – czyli szansę na zajście jakiegoś zdarzenia.

Pierwszy przykład jest z gatunku rozrywkowo-medialnych i związany jest z pewnym teleturniejem, który zresztą był kiedyś emitowany także w Polsce. Oto w pewnym jego etapie uczestnik jest konfrontowany z trzema zasłoniętymi bramkami, z których jedna zawiera nagrodę, a dwie pozostałe są puste. Spośród tej trójki gracz wybiera jedną bramkę, by stać się właścicielem jej ewentualnej zawartości. Trik polega na tym, że gospodarz programu – już po wyborze gracza – odsłania jedną z pozostałych bramek, która okazuje się być pusta. Zgodnie z regułami teleturnieju gracz może w tym momencie zmienić swój wybór i wskazać trzecią bramkę zamiast tej wybranej pierwotnie. Pytanie brzmi: czy taka zamiana mu się opłaca?
Część ludzi stwierdziłaby zapewne, że nie ma to znaczenia, bo szansa wygranej przecież i tak wynosi 1 do 3, bo tylko za jedną bramką jest nagroda. Inni mogliby uznać, że po odsłonięciu jednej bramki wybieramy już spośród dwóch, więc nasze szansę rosną do 50% – też niezależnie od tego, czy zmienimy swój pierwotny wybór czy nie… A jak jest naprawdę?
Może się to wydawać niedorzeczne, jednak będąc na miejscu gracza, powinniśmy zawsze zmienić swój wybór. Mało tego, w ten sposób nasze szanse na wygraną rosną dokładnie dwukrotnie! Jak to możliwe?… Otóż kluczowe w wyjaśnieniu tego zjawiska jest zauważenie, że gospodarz programu zawsze odsłoni bramkę pustą i niewybraną przez gracza (w innym przypadku gra skończyłaby się od razu i w ogóle nie byłoby możliwości zmiany). Dlatego też opłaca się dokonać zmiany, bo w ten sposób w istocie odwracamy prawdopodobieństwo wygranej i przegranej. Możliwe są bowiem dwie sytuacje:

• gracz początkowo wybiera bramkę z nagrodą – po zmianie kończy więc z bramką pustą
• gracz najpierw wskazuje bramkę pustą; wówczas gospodarz odsłoni drugą pustą bramkę, więc zmiana skończy się wyborem bramki z nagrodą

Jak wiadomo prawdopodobieństwo dobrego wyboru spośród trzech bramek wynosi 1/3, a złego – 2/3. Takie są też odpowiednie prawdopodobieństwa dwóch powyższych scenariuszy; innymi słowy, zmiana bramki powoduje, że prawdopodobieństwo wygranej rośnie z początkowego 1/3 do 2/3.
Jeśli ktoś ma nadal wątpliwości, to nie ma czym się martwić – podobno wielu matematyków też ma kłopoty z ogarnięciem tego paradoksu :) Wydaje mi się, że rzecz w tkwi w błędnym określeniu, co tak naprawdę jest tutaj zdarzeniem losowym. Jeśli za takie będziemy uważali zarówno początkowy wybór, jak i zmianę, to rzeczywiście mogą być kłopoty z dojściem do poprawnych wniosków. Zamiast tego całą grę powinno się traktować jako jedno doświadczenie losowe, ze z góry ustalonym scenariuszem.

A co z drugim przykładem? Jest na szczęście nieco prostszy i dotyczy koncepcji zdarzeń (nie)zależnych. Oto kilka pytań dotykających tej kwestii, dla których odpowiedzi “intuicyjne” są zwykle błędne:

• Jeśli zakręcimy kołem ruletki 57 razy i za każdym razem kulka wpadnie w czarne pole, to jaka jest szansa na to, że będzie tak również przy następnym obrocie?
• Jeśli liczba 42 ostatni raz wystąpiła w Dużym Lotku pół roku temu, to jaka jest szansa, iż wypadnie w dzisiejszym losowaniu?
• Jeśli w grze X potwór Y wyrzuca przedmiot Z z prawdopodobieństwem 1/n, to jak dużo potworów Y powinienem zabić, aby być prawie pewien, że wypadnie mi z nich przedmiot Z?

Nie, prawdopodobieństwo wpadnięcia kulki w czarne pole to cały czas 1/2. Nie, liczba 42 może wypaść z takim samym prawdopodobieństwem dzisiaj, jak i w każdym innym losowaniu. Nie, zabicie n potworów Y wcale nie da nam prawie-pewności dostania Z – o ile mówimy o zwyczajowym użyciu słowa ‘prawie’ ;)
Wszędzie tutaj mamy bowiem do czynienia z sekwencją zdarzeń całkowicie niezależnych, których wyniki nie wpływają na siebie. Zatem nie ma znaczenia to, ile razy wcześniej kręciliśmy ruletką, ile wysłaliśmy już w życiu kuponów Lotto i ile wrażych monstrów zdołaliśmy zaszlachtować – prawdopodobieństwo zajścia interesującego nas zdarzenia w kolejnej próbie jest zawsze identyczne. Możemy aczkolwiek spróbować policzyć, na ile jest to prawdopodobne dla ciągu k kolejnych prób. Otóż ze schematu Bernoulliego wynika, że szansa na sukces wynosi wtedy

1 – (1 – p)^k

jeśli dla pojedynczej próby prawdopodobieństwo wynosi p. Stąd dla p = 1/n i k = n otrzymujemy (po kilku, jak to by powiedzieli matematycy, “trywialnych przekształceniach ;D) wynik: (e – 1)/e; nieco ponad 63%. To trochę mało jak na prawie-pewność, czyż nie? ;]

Jak więc widać na przykładach, szansa na to, że opacznie zrozumiemy sytuację, w której zastosowania mają pojęcia ‘szansy’ czy ‘prawdopodobieństwa’ (używane tutaj jako synonimy) jest – nomen omen dosyć duża. Może dlatego w szkole niespecjalnie przepadałem za tym działem matematyki :)

Losowanie tabelkowe

W niemal każdym programie chociaż raz zdarza się potrzeba, by “rzucić kośćmi” i pozwolić, by wydarzyło się coś losowego. Oznacza to skorzystanie z generatora liczb pseudolosowych, aby uzyskać ‘przypadkową’ wartość. Nie będzie ona faktycznie losowa, lecz dzięki zastosowaniu matematycznych formuł o dużej nieregularności rezultat może być bardzo zbliżony do ideału. Istnieje oczywiście wiele algorytmów wyznaczania liczb pseudolosowych, różniących się faktyczną przypadkowością uzyskiwanego wyniku.
W różnych językach programowania mamy natomiast odmienne sposoby na uzyskanie liczby ‘losowej’. Zwykle najwygodniejszym jest wartość z zakresu [0..1], bo odpowiada to matematycznemu pojęciu prawdopodobieństwa. Aby w C++ uzyskać taki rezultat, wystarczy napisać proste opakowanie na biblioteczną funkcję rand:

Mając taki generator, możemy już łatwo sprawdzić, czy “zdarzyło się” coś, czego prawdopodobieństwo znamy:
// doświadczenie losowe z określonym prawdopodobieństwem
bool RandomOccured(float fProbability) { return Random() <= fProbability; }[/cpp] W ten sposób możemy na przykład rzucać wirtualną monetą. Sprawa się jednak komplikuje, jeżeli możliwych wyników doświadczenia jest więcej, a przy okazji mają one różne prawdopodobieństwa zajścia. Tak się dzieje na przykład w grach RPG, w których konieczne jest obliczanie rezultatów zadanych ciosów (trafienie, pudło, unik, blok, itp.). Skuteczność postaci w walce zależy zwykle od jej statystyk, więc szanse poszczególnych wyników nie są stałe i zmieniają się w trakcie gry.
Dobre generatory liczb pseudolosowych są zaś nierzadko względnie kosztowne obliczeniowo. Dlatego zamiast wykonywać po jednym losowaniu dla każdego możliwego rezultatu (zaszedł – nie zaszedł), znacznie lepiej jest załatwić wszystko jednym losowaniem. Nie jest to trudne:
// doświadczenie losowe z prawdopodobieństwem określonym tabelką
int RandomResult(const float* aProbs, int n)
{
float fRand = Random();

float fAccum = 0.0f;
for (int = 0; i < n; ++i) { // sprawdzamy, czy wylosowana liczba mieści się w zakresie p-stwa if (fAccum <= fRand && fRand < fAccum + aProbs[i]) return i; fAccum += aProbs[i]; } // błąd return -1; }[/cpp] Tak naprawdę liczymy tutaj dla każdego możliwego rezultatu wartość tzw. dystrybuanty. Ale chyba nie warto wnikać w takie teoretyczne szczegóły – grunt, że powyższa metoda działa w praktyce :) Trzeba tutaj jednak pamiętać, aby prawdopodobieństwa sumowały się do 1. Jeśli tak nie jest, można przeskalować wylosowaną liczbę.