algorytm.org

Test Pi



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Test Pi
Ocena użytkowników:***** / 11
SłabyŚwietny 
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:
Test PI


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ę:
Test PI - uproszczenie


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
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiC#MS Visual Studio .net
.cs
.cs
***** / 2
Tomasz LubińskiC/C++
.cpp
.cpp
***** / 2
Tomasz LubińskiDelphi/Pascal
.pas
.pas
***** / 1
Tomasz LubińskiJava
.java
.java
***** / 2
Marek MadejskiPythonPython 3
.py
.py
***** / 1
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 03 października 2012 14:45
Dodaj komentarz