StartAlgorytmyLiczby pseudolosoweTest Pi
Baza Wiedzy
Wersja offline serwisu przeznaczona na urządzenia z systemem Android.

Darowizny
darowiznaWspomóż rozwój serwisu


Nagłówki RSS
Kanał artykuły
Kanał implementacje
Kanał komentarze
Kanał forum


Bookmarki









Sonda
Implementacji w jakim języku programowania poszukujesz?
 
Test Pi
Ocena użytkowników:++++- / 5
SłabyŚwietny 
Wpisany przez Tomasz Lubiński
poniedziałek, 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:
Isq / Ic = 4*r2 / pi*r2


Jeżeli teraz z tego równania wyznaczmy pi, to otrzymamy:
pi = 4*Ic / Isq


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: (x-m/2)2 + (y-m/2)2 ≤ (m/2)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:
Isq / Ic = 0.25*4*r2 / 0.25*pi*r2


Jeżeli teraz z tego równania wyznaczmy pi, to otrzymamy dokładnie taką samą zależność jak poprzednio:
pi = 4*Ic / Isq


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.




Autor Język programowania Komentarz Otwórz Pobierz Ocena
Tomasz Lubiński C# MS Visual Studio .net
Implementacja w C#
Implementacja w C#
++++- / 2
Tomasz Lubiński C/C++
Implementacja w C/C++
Implementacja w C/C++
+++-- / 2
Tomasz Lubiński Delphi/Pascal
Implementacja w Delphi/Pascal
Implementacja w Delphi/Pascal
++++- / 1
Tomasz Lubiński Java
Implementacja w Java
Implementacja w Java
++++- / 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: wtorek, 21 czerwca 2011 17:55

Dodaj komentarz

Kod antysapmowy
Odśwież