Porównanie wydajności algorytmów obliczania Pi (MPFR)
Zaimplementowałem 5 popularnych algorytmów obliczania liczby Pi przy użyciu biblioteki MPFR (dla dowolnej precyzji) w języku C. Przeprowadziłem testy wydajnościowe dla precyzji od 100 do 100 000 cyfr dziesiętnych.
Zaimplementowane algorytmy
- Newton (arcsin 1/2) – Szereg Taylora dla $\arcsin(1/2) = \pi/6$. Zbieżność liniowa, daje około 1 bit precyzji na iterację.
- Machin (1706) – Wzór oparty na $\arctan$: $\pi/4 = 4\arctan(1/5) – \arctan(1/239)$. Zbieżność liniowa, szybsza od Newtona (~1.4 cyfry dziesiętnej na iterację).
- Borwein (AGM, 1984) – Algorytm iteracyjny oparty na średniej arytmetyczno-geometrycznej. Zbieżność kwadratowa (liczba poprawnych cyfr podwaja się w każdej iteracji).
- Chudnovsky (1989) – Zbieżność liniowa, ale niezwykle szybka: każda iteracja dostarcza ponad 14 cyfr dziesiętnych. Używany w większości współczesnych rekordów bicia Pi.
- BBP (Bailey-Borwein-Plouffe, 1995) – Słynny wzór szesnastkowy. Zbieżność liniowa (~1.2 cyfry hex na iterację).
Wyniki dla 10 000 cyfr dziesiętnych
Poniższa tabela przedstawia czas obliczeń oraz liczbę iteracji potrzebną do uzyskania 10 000 poprawnych cyfr Pi.
| Algorytm | Czas obliczeń [s] | Liczba iteracji | Szybkość [cyfry/s] | Zbieżność |
| Borwein (AGM) | 0.0037 | 7 | ~2 699 922 | Kwadratowa |
| Chudnovsky | 0.0748 | 707 | ~133 738 | Liniowa (14.18 cyfr/it) |
| BBP | 0.1263 | 8 300 | ~79 191 | Liniowa (1.2 cyfr/it) |
| Machin (arctan) | 0.4674 | 9 255 | ~21 392 | Liniowa (1.4 cyfr/it) |
| Newton (arcsin) | 1.5804 | 16 602 | ~6 326 | Liniowa (1 bit/it) |
(Testy wykonano w jednowątkowej implementacji C, na procesorze w środowisku sandboxowym)
Wizualizacja wyników
Czas obliczeń w funkcji precyzji
Poniższy wykres pokazuje skalowanie algorytmów (w skali logarytmicznej). Widzimy wyraźnie, że algorytm Borweina deklasuje pozostałe przy wysokich precyzjach dzięki kwadratowej zbieżności.
Zestawienie czasów (wykres słupkowy)
Wykresy dla różnych rzędów wielkości (od 100 do 10 000 cyfr). Zauważ, jak drastycznie rośnie czas metody Newtona względem nowocześniejszych algorytmów.
Szybkość generowania cyfr
Wykres pokazujący, ile poprawnych cyfr na sekundę potrafi wygenerować dany algorytm. Spadek dla większych precyzji wynika ze złożoności mnożenia dużych liczb w MPFR (złożoność $O(N \log N)$).
Więcej wyników – dla 100 000 cyfr: (testy na procesorze AMD Ryzen 5 3600, 64 GB RAM. OS Ubuntu 64 bit)
============================================================ Pi Benchmark — MPFR | prec = 332200 bits (~100002 dec. digits) ============================================================ Reference (mpfr_const_pi, first 60 digits): 3.141592653589793238462643383279502884197169399375105820974945 Algorytm Czas [s] Iteracje Poprawne cyfry Zbieżność -------------------------------- ---------- ---------- -------------- -------------- Newton (arcsin 1/2) 337.892078 166089 100000.3 liniowa Machin (arctan 1/5, 1/239) 78.083924 92557 99999.8 liniowa Borwein kwadr. (AGM) 0.096225 9 99997.2 kwadratowa Chudnovsky 14.131964 7054 100000.0 liniowa BBP (Bailey-Borwein-Plouffe) 7.968434 83044 99999.8 liniowa Algorytm Cyfry/iter Cyfry/sek -------------------------------- ---------- --------- Newton (arcsin 1/2) ~1 bit/iter 296 Machin (arctan 1/5, 1/239) ~1.4 cyfry/iter 1281 Borwein kwadr. (AGM) podwaja cyfry 1039199 Chudnovsky ~14.18 cyfr/iter 7076 BBP (Bailey-Borwein-Plouffe) ~1.2 cyfry hex/iter 12549 Note: 'Poprawne cyfry' = liczba cyfr dziesiętnych zgodnych z mpfr_const_pi.
Wnioski
- Metoda Newtona jest historycznie ważna i elegancka, ale numerycznie najwolniejsza ze wszystkich testowanych. Potrzebuje aż 16 602 iteracji, by osiągnąć 10 000 cyfr, co zajęło ponad 1.5 sekundy.
- Algorytm Chudnovsky’ego to król metod opartych na szeregach. Dzięki dodawaniu ponad 14 cyfr w każdym kroku, potrzebował zaledwie 707 iteracji do osiągnięcia 10 000 cyfr.
- Algorytm Borweina (AGM) całkowicie deklasuje konkurencję w prostej implementacji bez optymalizacji binary splitting. Kwadratowa zbieżność sprawia, że w zaledwie 7 iteracjach obliczył 10 000 cyfr Pi w czasie 0.0037 sekundy (ponad 400 razy szybciej niż metoda Newtona).
- W profesjonalnych programach (np. y-cruncher) do bicia rekordów świata (tryliona cyfr) używa się wzoru Chudnovsky’ego, ponieważ można go bardzo wydajnie zrównoleglić i zoptymalizować techniką binary splitting, która omija potrzebę wyliczania wielu pierwiastków (co jest wąskim gardłem AGM w astronomicznych precyzjach). W prostej, jednowątkowej pętli AGM wygrywa.
Przypisy:
Pi Formulas – MATH WORLD WOLFRAM: https://mathworld.wolfram.com/PiFormulas.html
Kod źródłowy aplikacji BENCHMARK PI MPFR w języku c: https://github.com/SylwesterBogusiak/ComputePi/blob/main/pi_bench.c
Opracowanie przy pomocy MANUS AI.