Wpisany przez Tomasz Lubiński,
06 października 2008 21:36
Test Pi (Test Π), jest prostym sposobem na sprawdzenie czy liczby losowane przez generator są
jednorodnie rozłożone dla danego zakresu. Na początku rozpatrzmy kwadrat oraz wpisane w niego koło:
Kolejne liczby losowe będziemy traktować jako współrzędne kolejnych punktów. Liczbę punktów które znajdują się wewnątrz kwadratu oznaczymy jako: Isq - tak na prawdę będą to wszystkie wygenerowane przez nas punkty. Natomiast liczbę punktów, które znajdują się wewnątrz koła oznaczymy jako Ic.
Zauważmy, że stosunek liczby punktów wewnątrz kwadratu do liczby punktów wewnątrz koła powinien, przy równomiernym rozłożeniu punktów być równy stosunkowi pola kwadratu do pola koła. Zatem, jeżeli promień koła oznaczymy jako r otrzymamy następujące równanie:
Jeżeli chcemy sprawdzić generator losujący liczby z przedziału od 0 do m wówczas otrzymamy następujące warunki na obliczenie liczby punktów w figurach:
Wzór ten można nieco uprościć. Załóżmy, że początek koła znajduje się w punkcie (0, 0), a my rozpatrywać będziemy tylko jedną ćwiartkę opisanego poprzednio przypadku. Uzyskamy zatem następującą sytuację:
Oznaczenia, pozostaną takie same jak poprzednio, zmienią się tylko powierzchnie figur:
Cały algorytm tesu Pi możemy przedstawić następująco:
Należy też zauważyć, iż nawet przy idealnym generatorze i bardzo dużej liczbie losowanych punktów liczbę Pi możemy wyznaczyć jedynie w pewnym przybliżeniu. Ograniczać nas będzie tutaj reprezentacja liczb zmiennoprzecinkowych w komputerze. I tak dla liczb pojedynczej precyzji będzie to około 6 cyfr przecinku a dla liczb podwójnej precyzji będzie to około 15 cyfr po przecinku.
Test Pi oparty jest na tych samych spostrzeżeniach co całkowanie numeryczne metodą Monte-Carlo.
Kolejne liczby losowe będziemy traktować jako współrzędne kolejnych punktów. Liczbę punktów które znajdują się wewnątrz kwadratu oznaczymy jako: Isq - tak na prawdę będą to wszystkie wygenerowane przez nas punkty. Natomiast liczbę punktów, które znajdują się wewnątrz koła oznaczymy jako Ic.
Zauważmy, że stosunek liczby punktów wewnątrz kwadratu do liczby punktów wewnątrz koła powinien, przy równomiernym rozłożeniu punktów być równy stosunkowi pola kwadratu do pola koła. Zatem, jeżeli promień koła oznaczymy jako r otrzymamy następujące równanie:
\frac{I_{sq}}{I_c} = \frac{4*r^2}{\pi*r^2}
Jeżeli teraz z tego równania wyznaczmy pi, to otrzymamy:
\pi = \frac{4*I_c}{I_{sq}}
Im równomierniej rozłożone są losowane punkty, tym z większą dokładnością wyznaczmy liczbę pi. I na tym dokładnie polega ten test. Porównaniu podlega znana wartość pi = 3.141592653589793238462643383279502884197169399..., z wartością wyznaczą za pomocą powyższego wzoru.Jeżeli chcemy sprawdzić generator losujący liczby z przedziału od 0 do m wówczas otrzymamy następujące warunki na obliczenie liczby punktów w figurach:
- Isq - liczba wygenerowanych punktów
- Ic - liczba punktów (x, y) spełniających warunek:
\left(x-\frac{m}{2}\right)^2 + \left(y-\frac{m}{2}\right)^2 \leq; \left(\frac{m}{2}\right)^2
Wzór ten można nieco uprościć. Załóżmy, że początek koła znajduje się w punkcie (0, 0), a my rozpatrywać będziemy tylko jedną ćwiartkę opisanego poprzednio przypadku. Uzyskamy zatem następującą sytuację:
Oznaczenia, pozostaną takie same jak poprzednio, zmienią się tylko powierzchnie figur:
\frac{I_{sq}}{I_c} = \frac{0.25*4*r^2}{0.25*\pi*r^2}
Jeżeli teraz z tego równania wyznaczmy pi, to otrzymamy dokładnie taką samą zależność jak poprzednio:
\pi = \frac{4*I_c}{I_{sq}}
Jeżeli chcemy sprawdzić generator losujący liczby z przedziału od 0 do m wówczas otrzymamy następujące warunki na obliczenie liczby punktów w figurach:
- Isq - liczba wygenerowanych punktów
- Ic - liczba punktów (x, y) spełniających warunek: x2 + y2 ≤ m2
Cały algorytm tesu Pi możemy przedstawić następująco:
int n; //liczba losowanych punktow
double x, y; //wspolrzedne losowanych punktow
double m; //zakres losowanych liczb
int Isq, Ic; //liczby punktow w kwadracie oraz kole
Isq = 0;
Ic = 0;
while (Isq < n)
{
x = rand();
y = rand();
Isq = Isq + 1;
if (x*x + y*y <= m*m) then Ic = Ic + 1;
}
pi = 4.0*Ic / Isq;
Należy też zauważyć, iż nawet przy idealnym generatorze i bardzo dużej liczbie losowanych punktów liczbę Pi możemy wyznaczyć jedynie w pewnym przybliżeniu. Ograniczać nas będzie tutaj reprezentacja liczb zmiennoprzecinkowych w komputerze. I tak dla liczb pojedynczej precyzji będzie to około 6 cyfr przecinku a dla liczb podwójnej precyzji będzie to około 15 cyfr po przecinku.
Test Pi oparty jest na tych samych spostrzeżeniach co całkowanie numeryczne metodą Monte-Carlo.
Implementacje
Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
Tomasz Lubiński | C# | MS Visual Studio .net | .cs | .cs | ***** / 2 |
Tomasz Lubiński | C/C++ | .cpp | .cpp | ***** / 2 | |
Tomasz Lubiński | Delphi/Pascal | .pas | .pas | ***** / 1 | |
Tomasz Lubiński | Java | .java | .java | ***** / 2 | |
Marek Madejski | Python | Python 3 | .py | .py | ***** / 1 |
Poprawiony: 03 października 2012 14:45