niedziela, 22 stycznia 2017

"Zasiewanie" z zadaną gęstością (CA)

Wracamy dziś do jednowymiarowego automatu komórkowego (ang. Cellular Automaton, stąd skrót CA). Program opiera się niemal w całości na poprzednim przykładzie z jedną różnicą - zamiast pojedynczego ziarna automatu umieszczonego w środku "tablicy świata" wprowadzamy możliwość początkowego zasiania tablicy losowo z zadaną gęstością.

Sprowadza się to do jednego dodatkowego parametru modelu (IDens) oraz jednej pętli w procedurze setup(). Reszta kodu pozostaje niemal bez zmian. Czym się różni, zobaczycie, jeśli zaimplementujecie dokładnie ten powyższy kod.

wtorek, 17 stycznia 2017

Obliczanie Pi - przyśpieszone

A teraz obiecana przyśpieszona wersja programu obliczającego liczbę Pi metodą Monte Carlo:

Pierwotny program na moim laptopie wykonywał ok 1500 losowań na sekundę. Ten jest 1000 razy szybszy! Wykonuje około 1500000 losowań na sekundę. Składa się na to kilka modyfikacji:

W obrębie procedury draw() wstawiona jest pętla wykonująca pewną liczbę losowań (zmienna nst) w każdym wywołaniu. Dzięki temu zmniejszamy czas obsługi okna odbywającej się w związku z każdym wywołaniem draw(). Zamiast 1500 takich operacji mamy trochę ponad 70, przy nst == 20000. Czyli program losuje punkty i wrzuca je na wewnętrzną reprezentację grafiki okna, a okno odświeża nie 1500, ale jedynie 75 razy na sekundę. To daje gigantyczną oszczędność!
W procedurze setup() wyłączamy wygładzanie grafiki za pomocą noSmooth() .
Skoro rysujemy pojedyncze punkty to jest ono zbędne, a nawet niepożądane. Ta modyfikacja daje jeszcze około pięciokrotne przyśpieszenie
Zamiast losować składową koloru i odcień szarości dla wizualizowanych punktów używamy reszty z dzielenia (operator %). Jest to operacja dużo szybsza niż uzyskanie kolejnej liczby pseudolosowej, a efekt wizualny jest nieodróżnialny - i tak losujemy pozycje punktów, więc to że kolory mają sekwencyjne odcienie jest nie do zauważenia. Przy okazji oszczędzamy też liczbę wywołań generatora pseudolosowego co przy miliardach nawrotów pętli może mieć znaczenie (ale to temat na osobny post, a nawet kilka wpisów)
Tak znaczące przyśpieszenie programu pozwala osiągnąć w rozsądnym czasie kilka miliardów losowań. I tu pojawia się problem, bo w zakresie liczby typu int (32 bity ze znakiem) mieści się zaledwie trochę ponad 2 miliardy. A potem, czyli przy kolejnym powiększeniu o 1, liczba ta się przewija i staje UJEMNA! Nie ma sensu dalej liczyć. Stąd sprawdzamy w programie kiedy nastąpi ten moment i wyłączamy dalsze wywołania pętli draw() za pomocą noLoop();
Ale przedtem obliczamy uzyskaną wartość Pi i wyświetlamy w oknie graficznym czcionką o rozmiarze 18 pkt.

Oto wynik działania:

Tak oto uzyskaliśmy bardzo szybki program, aczkolwiek jego dokładność nie jest oszałamiająca. Wynika to z ograniczeń zastosowanych typów - float i int. Można by dokładność zwiększyć używając pojemniejszych typów - na początek także standardowe double i long. Ale to by rodziło kolejne problemy, bo są to typy języka Java nie do końca wspierane przez Processing.
Tak więc o ich stosowaniu będzie innym razem.

poniedziałek, 16 stycznia 2017

Obliczanie liczby Pi metodę Monte Carlo

"Metoda Monte Carlo (MC) jest stosowana do modelowania matematycznego procesów zbyt złożonych, aby można było przewidzieć ich wyniki za pomocą podejścia analitycznego.
Istotną rolę w metodzie MC odgrywa losowanie (wybór przypadkowy) wielkości charakteryzujących proces, przy czym losowanie dokonywane jest zgodnie z rozkładem, który musi być znany."

Oryginalny przykład w Wikipedii jest napisany w C++:

#include <iostream>
#include <cmath>
#include <ctime>
#include <cstdlib>
using namespace std;
int main()
{
     srand(time(NULL)); //zainicjalizowanie maszyny generujacej liczby pseudolosowe
     int n;
     int nk = 0;
     double x,y;
     float s;
     
     cout << "Podaj liczbe losowanych pkt:" << endl;
     cin >> n;

     for(int i = 1; i <= n; i++)
     {           
         x = ((double)rand() / (RAND_MAX)) * 2 - 1;
         y = ((double)rand() / (RAND_MAX)) * 2 - 1;
         if(x*x + y*y <= 1)
         {
             nk++;
         }
     }
     
     cout << "Liczba pkt. w kole wynosi: " << nk << endl;
     cout << "Liczba pkt. w kwadracie wynosi: " << n << endl;
     s = 4. * nk / n;
     cout << "Liczba pi wynosi: " << s;
}

Jednak przerobienie go na Processing trwa chwilę i gdyby nie dodanie wyświetlania to kod byłby nawet prostszy.

Kilka elementów jest tu warte uwagi.

Po pierwsze zniknęła główna pętla, bo została zastąpiona przez niejawną pętle wywołań funkcji draw() (od linii 24). Liczbę wywołań tej funkcji życzymy sobie mieć jak największą, zatem w funkcji setup() deklarujemy frameRate na 10000. To jednak oczywiście tylko "pobożne życzenie" - nie sądzę żeby udało się to na komputerze jaki macie do dyspozycji
Ponadto znacznie uprościły się instrukcje losowania x i y (linie 26 i 27). Sam język daje nam do dyspozycji funkcję random(float), która może zwracać liczbę w zakresie 0..1, co w C++ uzyskiwaliśmy przez dzielenie rand()/RAND_MAX;
A obliczenia wartości Pi wykonujemy nie na końcu programu, lecz za każdym razem gdy operator naciśnie jakiś klawisz na klawiaturze. Służy temu funkcja obsługi zdarzenia keyPressed(). Wyniki jej działania pojawiają się nie w oknie programu lecz na konsoli tekstowej. W szczególności dzięki predefiniowanej w Processingu zmiennej frameRate możemy dowiedzieć się ile naprawdę punktów na sekundę oblicza nasz program.
Wreszcie korzystając z tego, że w przeciwieństwie do C++ mamy od razu do dyspozycji okno graficzne rysujemy też wylosowane punkty, a właściwie 1/4 z nich - te które mają obie współrzędne dodatnie. Dzięki użyciu liczby losowej w kolorach cały czas będzie widać postęp działania programu, także wtedy, gdy już każdy punkt okna zostanie co najmniej raz zamalowany.

Uruchomienie tego programu zajmie wam chwilę. Niestety uzyskanie sensownego przybliżenia liczby Pi będzie trwało znacznie dłużej. Ten program nie grzeszy szybkością. Głównym ograniczeniem jest liczba wywołań draw(). Na moim, dosyć starym komputerze nie udaje uzyskać więcej niż ok. 1500 wywołań draw() w ciągu sekundy.
Ale każde wywołanie draw() wiąże się z obsługą ekranu - co jest czasochłonne.
To daje nam furtkę do znaczącego przyśpieszenia obliczeń w tym programie.

SAMI WYMYŚLCIE JAK! ROZWIĄZANIE W NASTĘPNYM POŚCIE
POWODZENIA!

Reference - czyli co jest nam dane

W przeciwieństwie do C,C++ czy Javy język Processing jest zorientowany na grafikę, stąd większość jego elementów właśnie do grafiki się odnosi. Natomiast z punktu widzenia struktur czysto syntaktycznych jest w porównaniu z językami ogólnymi mocno zubożony - w szczególności w obszarze programowania obiektowego. Jednak zawsze można użyć klasy wykonanej bezpośrednio w języku Java i to zadziała.
Aktualna składnia jezyka (już w wersji 3) i zawartość jego biblioteki standardowej jest dostępna z tej listy:
https://processing.org/reference/