Parę słów o liczbach losowych

Komputery są fajne. W pół sekundy umieją policzyć ile jest 42363 * 1234 a w czasie wyświetlania wyniku mogą przy okazji puścić ulubioną empetrójkę. Niestety, w pewnym sensie komputery są jak inteligentny, choć nudny sąsiad na imprezie. Bez problemu powie Ci, jaka jest stolica Paragwaju, ale kiedy przychodzi zrobić coś naprawdę szalonego, nie masz co na niego liczyć. Rozłoży bezradnie ręce i głupawo się uśmiechnie. Dobrze, ale dlaczego komputer miałby robić coś szalonego?

Okazuje się, że komputerom czasem przydałoby się nieco nieprzewidywalności. Kiedy grasz w Sapera, to liczysz na to, że miny będą za każdym razem w innych miejscach – inaczej gra byłaby równie ciekawa, jak rozmowa z zegarynką. Odrobina nieprzewidywalności przydaje się też w poważniejszych sytuacjach. Gdy kupujesz w Internecie roczny zapas Pepsi, wpisując swój numer karty kredytowej, to naprawdę liczysz na to, że nikt inny tych danych nie podejrzy. Komputer szyfruje całą Twoją komunikację, wykorzystując pewne dane losowe jako tak zwany klucz.

Komputer. Dane losowe. Jest w tych dwóch sformułowaniach jakaś sprzeczność (coś jakby „Mój Nudny Znajomy Z Imprezy” i „Rowerowa Wycieczka Po Pustyniach Ameryki Południowej”). Komputer wykonuje ścisłe polecenia: weź tę liczbę, dodaj to tamtej, pomnóż wynik i wyświetl to na ekranie. Te operacje łatwo mu zdefiniować. Ale jak zmusić go, by coś wylosował? Odpowiedź jest bardzo prosta: nie da się.

Po prostu, nie da się zapisać algorytmu losowania liczby, dlatego, że liczba losowa z definicji nie jest generowana żadnym algorytmem. Oczywiście miłośnicy Sapera odezwą się: hola hola, przecież komputer układa mi te miny za każdym razem w inny, losowy sposób. Prawda. Jednak nie jest to sposób losowy, a pseudolosowy. Coś jak z tą demokracją i demokracją ludową.

Istnieją pewne funkcje matematyczne, których kolejne wartości są bardzo dziwne, pozornie niezwiązane ze sobą. Nie tak jak stary dobry sinus, co się wiecznie powtarza, czy logarytm, który nie chce dorosnąć. Są to dziwne funkcje, których wartość raz wynosi 12, w kolejnym kroku 54 a za chwilę znowu 37. Ktoś kto przyjrzałby się z boku takiej funkcji, nie znając jej wzoru, krzyknąłby: „te liczby nie mają żadnego związku, wyglądają jakby były losowe”. Słusznie, takie jest ich zadanie.

Komputery, gdy prosi się je, by podały nam liczbę losową, podają po prostu kolejną wartość takiej funkcji. A my, naiwni, wierzymy, że wartość ta rzeczywiście jest dziełem przypadku. Warto zwrócić uwagę, że każda taka funkcja losowa musi od czegoś zacząć. Inaczej mówiąc: musimy komputerowi podać pierwszą liczbę (ziarno), żeby na jej podstawie wygenerował kolejną. Jeśli podamy dwa razy tę samą liczbę jako ziarno, wówczas otrzymamy ten sam rozkład min na mapie. Ziarno więc powinno być w jakiś sposób losowe.

Dochodzimy do punktu wyjścia: skąd do … wziąć liczbę, którą podamy jako owe ziarno? Można użyć się na przykład bieżącego czasu (Saper uruchomiony o tej samej godzinie na innym komputerze będzie miał miny w tym samym miejscu), dla kolegów informatyków zapiszę ten pomysł jako

srand(time(NULL));

Inni używają na przykład temperatury procesora, czy danych na temat brzęczenia dysku twardego – uciekamy się więc do świata rzeczywistego, który jest naprawdę nieprzewidywalny (świetnym przykładem jest MZK Toruń, w szczególności linia nr 15). Wszystko to jednak nieco koślawe.

W świecie Internetu można by w elegancki sposób rozwiązać ten problem. Dlaczegóż by nie posadzić 100 osób, by rzucały setką kostek do gry, wpisywały wyrzucone liczby do komputera i zamieszczały je w Internecie, jako liczby rzeczywiście losowe, które każdy mógłby sobie ściągnąć? Pomysł ten został zresztą zrealizowany (z tym, że bez kostek, no i bez 100 osób).

Każde dziecko wie, że najbardziej nieprzewidywalną rzeczą na świecie jest pogoda (no, oprócz kobiet, ale je ciężko podłączyć do komputera). Wiedzą to i twórcy serwisu random.org, który pobiera tak zwany szum atmosferyczny i przetwarza go na eleganckie liczby. Serwis Prawdziwie Losowych Liczb – oto slogan owej strony (brzmi niczym nazwa strony z ocenami z egzaminu z Programowania Równoległego).

Od pogody jest jednakże coś bardziej nieprzewidywalnego – jest to atom promieniotwórczy. Ha! Zabrzmiało groźnie. Otóż taki atom promieniotwórczy może się rozpaść. Może też się nie rozpaść. O tym, czy w danej chwili atom się rozpadnie czy nie, wie tylko on sam. My, jako ludzie XXI wieku znamy prawdopodobieństwo zajścia jednego lub drugiego zdarzenia, ale to wszystko. Taki atom świetnie zastępuje osobę rzucającą kostką do gry, a urządzenie z większą ilością atomów mądrzy ludzie podłączyli do komputera i wyniki przesyłają na żądanie w serwisie hotbits. Atomowy saper – to jest gra warta napisania.

OK, wszyscy humaniści mogą się już oddalić, zaś miłośnikom języka Ruby polecam bibliotekę RealRand, która daje wygodny interfejs do obu serwisów:

require 'random/online'

generator1 = Random::RandomOrg.new
generator1.proxy_host = 'your.proxy.here'
generator1.proxy_port = 8080
generator1.proxy_usr  = 'your.user.here'
generator1.proxy_pwd  = 'secret'
puts generator1.randbyte(5).join(",")
puts generator1.randnum(100, 1, 6).join(",")  # Roll the dice 100 times.

7 myśli nt. „Parę słów o liczbach losowych

  1. dzkns

    ciekawie piszesz, ale chce zauwazyc, ze liczby losowe uzyskane przez np. rzucenie kostka do gry, sa tak samo „losowe” jak te wygenerowane przez komputer. W obu przypadkach korzystamy z faktu, ze bardzo ciezko nam jest przewidziec co wypadnie. Zauwaz, ze gdyby sie uprzec, to mozna by zmudnymi obliczeniami dojsc do tego jaka liczba wypadnie po rzucie kostka, biorac pod uwage mase czynnikow, ze tak to ujme „srodowiskowych”. Mysle, ze jest to tak samo trudne, jak trafienie na te milisekunde przez time(NULL) dla kilku roznych wywolan funkcji.

  2. Newton Autor wpisu

    @grucha
    Dzięki za link, właśnie oglądam sobie. Gość ciekawie opowiada 🙂

    @dzkns
    Owszem, ciężko przewidzieć i przy pojedynczych wylosowaniach nie ma różnicy. Jednak chodzi o to, że wynik rand() to tak naprawdę wynik pewnych matematycznych wzorów, więc między wylosowanymi liczbami istnieją zależności, możliwe do opisania przez statystykę. Przykład jest tutaj – wykresy utworzone z liczb pochodzących z nagłówka TCP, które to liczby powinny być teoretycznie losowe.

    Tymczasem rzuty kostką zapewniają większą „losowość”, gdyż nie ma tu żadnego wzoru. Gdyby taki wzór istniał, to musiałby zawierać jako zmienne wszystkie siły i cząstki obecne we wszechświecie, a z zasady nieoznaczoności wynika, że nie możemy poznać dokładnie wszystkich tych wartości.

  3. Newton Autor wpisu

    Ups, sory, coś mi się kliknęło i zdjąłem go ze strony głównej. Już jest.

  4. raj

    Wbrew pozorom istnieją programy dostarczające „prawdziwych” liczb losowych. Oczywiście opierają sie one na zewnętrznych przypadkowych danych jak: stany nieustalone pamięci, opóźnienia między kolejnymi pakietami przychodzącymi z sieci, operacjami odczytu dysku itp. itd. W Linuksie i wielu innych systemach operacyjnych takich „prawdziwych” liczb losowych dostarcza urządzenie /dev/random (obok tego istnieje również generator pseudolosowy – /dev/urandom). Dla Windows a nawet DOS-a (!) istnieją specjalne sterowniki działające w podobny sposób.
    Wcale nie trzeba kombinowac z sięganiem do jakichś zewnętrznych serwisów.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *