Strona główna » Algorytmy » Artykuły » Wyznaczanie liczby π
π
 

Wyznaczanie liczby π

https://mattomatti.com/a84

Wstęp

Liczba π jest używana w matematyce do wielu różnych obliczeń. Do tej pory nie jest jasne ile ona tak naprawdę wynosi. Istnieje wiele różnych metod, które pozwalają je wyznaczyć, ale każda z nich różni się wynikiem. W niniejszym artykule zostały przedstawione niektóre z nich.

Metoda Gauss–Legendre

Metoda Gauss–Legendre wykorzystuje w trakcie obliczeń właściwości średnich arytmetycznych oraz harmonicznych. Pozwala ona na wyznaczenie 45 milionów cyfr liczby π po zaledwie 25 iteracjach. Innymi słowy wystarczy zaledwie kilka iteracji, aby standardowe biblioteki wypisywały błędne wyniki nie z powodu ograniczeń metody wyznaczania, a metody przechowywania danych.

Algorytm najlepiej zapisać w postaci listy kroków:

  1. Inicjowanie zmiennych: , , oraz
  2. Kolejne instrukcje wykonuje się do momentu uzyskania konkretnej dokładności lub, jak to będzie zaimplementowane, określoną ilość razy:
  3. Na sam koniec wynik wystarczy podać przy pomocy wzoru

Implementacja

Podczas działania programu należy pamiętać, że wartość jest wykorzystywana w trzech kolejnych równaniach, dlatego należy zapamiętać jej wartość przed jej nadpisaniem. Metodę Gauss–Legendre realizuje poniższy kod:

  1. double piGaussLegendre(long int n) {
  2.   long double an = 1.0, bn = 1.0 / sqrt(2), tn = 0.25, pn = 1.0, a_pom;
  3.   while (n--) {
  4.     a_pom = an;
  5.     an = (an + bn) / 2;
  6.     bn = sqrt(a_pom * bn);
  7.     tn = tn - pn * pow(a_pom - an, 2);
  8.     pn *= 2;
  9.   }
  10.   return pow(an + bn, 2) / (4.0 * tn);
  11. }

(1.) Funkcja wykona tyle iteracji ile wskaże użytkownik, a nie np. do określonej precyzji. (2.) Inicjalizacja zmiennych zgodna z krokiem 1. oraz (3. - 9.) wykonywanie kolejnych kroków zgodnie z krokiem 2. (11.) Na koniec zwrócona zostaje wartość (krok 3.).

Testowanie funkcji

Funkcję można przetestować przy pomocy poniższej funkcji main(), która po uruchomieniu zapyta się ile iteracji ma zostać wykonanych.

  1. int main() {
  2.   long int n;
  3.   cout << "Podaj ilosc iteracji: ";
  4.   cin >> n;
  5.   cout << setprecision(10) << piGaussLegendre(n) << endl;
  6.   system("pause");
  7.   return 0;
  8. }

Przykładowo dla 2 iteracji program rzeczywiście zwraca bardzo dokładny wynik liczby π:

  1. 3.141592646

Metoda Brouncker'a

Metoda Brouncker'a opiera się na nieskończonym ułamku, który dla stopnia złożoności n = 5 wygląda następująco:

Innymi słowy w celu wyznaczenia wartości liczby π wystarczy obliczyć ułamek i pomnożyć go razy 4. Wyliczenie ułamka upraszcza fakt, że w każdym kolejnym ułamku jest 2 plus potęga liczby nieparzystej podzielona przez następny ułamek. Dla uproszczenia (oraz żeby obliczenia miały swój koniec) należy przyjąć, że n ułamek, na samym dole całego wyrażenia będzie miał wartość .

Implementacja

Obliczenia trzeba rozpocząć od ostatniego ułamka, a następnie stopniowo obliczać kolejne części. W ten sposób działa poniższy algorytm:

  1. double piBrouncker(long int n) {
  2.   double wartosc = 2;
  3.   for (; n >= 0; n--) {
  4.     wartosc = double((2 * n + 1) * (2 * n + 1)) / (2.0 + wartosc);
  5.   }
  6.   return 4.0 / (1.0 + wartosc);
  7. }

(1.) Funkcja przyjmuje tylko jeden argument n, który określa ile podułamków ma zostać wyliczonych. (2.) Wartość ostatniego ułamka jest ustawiona na 2. (3.) Dla każdego podułamka: (4.) oblicz kolejną wartość. Na koniec (5.) zwróć wynik ze wzoru.

Testowanie funkcji

Funkcję można przetestować przy pomocy poniższej funkcji main(). Po skompilowaniu i uruchomieniu program zapyta się ile podułamków ma zostać obliczonych:

  1. int main () {
  2.   long int n;
  3.   cout << "Podaj ilosc wyrazow do obliczenia: ";
  4.   cin >> n;
  5.   cout << setprecision(10) << piBrouncker(n) << endl;
  6.   system("pause");
  7.   return 0;
  8. }

Przykładowo dla 1000000 prób program wypisze przykładowo:

  1. 3.141800978

Należy jednak pamiętać, że wynik zależy tylko i wyłącznie od wylosowanych wartości, więc zwrócona wartość nawet dla takiej samej ilości prób nie musi być identyczna.

Metoda Monte Carlo

Metodę tę śmiało można określić niezbyt matematyczną. Mianowicie metoda ta opiera się na liczbie Ludolfina. Jest to liczba rzeczywista i niewymierna (tak samo jak π) i reprezentuje stosunek długości obwodu koła do jego średnicy (tj. wartość liczby π). Jednak do wyznaczania jej wartości używa się... losowania. Mianowicie, aby wyznaczyć liczbę π tą metodą najpierw należy narysować kwadrat jednostkowy, następnie wpisać w niego koło. Następnie przeprowadza się n prób. W każdej próbie losuje się pewien punkt, który należy do kwadratu. W trakcie prób należy zliczyć ile punktów leżało zarówno w kwadracie jak i w kole. Następnie w celu obliczenia wartości liczby π wystarczy skorzystać ze wzoru , gdzie T - ilość punktów leżąca w kole, a n - ilość prób.

Implementacja

W programie zostało przyjęte, że kwadrat jednostkowy ma punkty o współrzędnych: {(0, 0), (0, 1), (1, 1), (1, 0)}. Wpisane koło w kwadrat można opisać wtedy przy pomocy równanie . Wtedy kod programu może mieć następującą postać:

  1. double piMonteCarlo(long int n) {
  2.   double x, y;
  3.   long int T = 0;
  4.   for (long int i = 0; i < n; i++) {
  5.     x = double(rand()) / RAND_MAX - 0.5;
  6.     y = double(rand()) / RAND_MAX - 0.5;
  7.     if (x*x + y*y <= 0.25) {
  8.       T++;
  9.     }
  10.   }
  11.   return 4 * double(T) / n;
  12. }

(1.) Funkcja przyjmuje jedynie ile prób ma zostać przeprowadzonych. (2. - 3.) Deklaracja zmiennych: x, y - będą przechowywać pozycję wylosowanego punktu, a T będzie zliczać ilość punktów trafionych w okrąg. Następnie (4.) przeprowadź n prób: (5. - 6.) wylosuj punkt i (7.) sprawdź czy leży w kole. Jeśli tak to (8.) zwiększ licznik T. Na koniec (11.) zwróć wynik zgodnie z wzorem.

Testowanie funkcji

Funkcję można przetestować przy pomocy poniższej funkcji main(), która po uruchomieniu zapyta się ile prób ma zostać przeprowadzonych.

  1. int main () {
  2.   srand(time(NULL));
  3.   long int n;
  4.   cout << "Podaj ilosc prob: ";
  5.   cin >> n;
  6.   cout << setprecision(10) << piMonteCarlo(n) << endl;
  7.   system("pause");
  8.   return 0;
  9. }

Przykładowo dla 1000000 prób program wypisze przykładowo:

  1. 3.144236

Należy jednak pamiętać, że wynik zależy tylko i wyłącznie od wylosowanych wartości, więc zwrócona wartość nawet dla takiej samej ilości prób nie musi być identyczna.

Zadania

Zadanie 1

Napisz wersje metody Gauss–Legendre, która pozwoli wyznaczać liczbę π do uzyskania konkretnej precyzji. Przykładowo dla precyzji 0.0001 program powinien wykonywać dalsze iteracje, aż 4 miejsca po przecinku nie zmienią się w następnej iteracji. Precyzję program powinien wczytać od użytkownika. Precyzja będzie podana w formacie 0.0..01, gdzie 0..0 to dowolna ilość zer.

Przykładowo dla precyzji 0.00001 program powinien wykonać n iteracji i pokazać następujący wynik:

  1. 3.141592654