Jak ustalić, czy moje obliczenia liczby pi są dokładne?

Próbowałem różnych metod do wdrożenia programu, który sekwencyjnie podaje cyfry pi. Próbowałem metody szeregowej Taylora , ale okazało się, że zbiega ona bardzo powoli (kiedy po pewnym czasie porównałem swój wynik z wartościami online). W każdym razie próbuję lepszych algorytmów.

Pisząc program, utknąłem w pewnym problemie, podobnie jak w przypadku wszystkich algorytmów: skąd mam wiedzieć, nże obliczone przeze mnie cyfry są dokładne?

Ponieważ jestem obecnie rekordzistą świata w zakresie większości cyfr liczby pi, dodam dwa centy :

O ile nie ustanawiasz nowego rekordu świata, powszechną praktyką jest po prostu weryfikacja obliczonych cyfr względem znanych wartości. To jest dość proste.

Mam stronę internetową z listą fragmentów cyfr w celu weryfikacji obliczeń w stosunku do nich: http://www.numberworld.org/digits/Pi/

Ale kiedy wejdziesz na rekord świata, nie ma nic do porównania.

Historycznie standardowym podejściem do sprawdzania poprawności obliczonych cyfr jest przeliczanie cyfr przy użyciu drugiego algorytmu. Więc jeśli jedno z obliczeń pójdzie źle, cyfry na końcu nie będą pasować.

Zwykle powoduje to ponad dwukrotność potrzebnego czasu (ponieważ drugi algorytm jest zwykle wolniejszy). Ale to jedyny sposób, aby zweryfikować obliczone cyfry, gdy wędrujesz na nieznane terytorium nigdy wcześniej nie obliczonych cyfr i nowego rekordu świata.

W czasach, gdy superkomputery ustawiały rekordy, powszechnie stosowano dwa różne algorytmy AGM :

• Algorytm Gaussa-Legendre'a
• Algorytm Borweina

Oba O(N log(N)^2)algorytmy były dość łatwe do wdrożenia.

Jednak w dzisiejszych czasach sytuacja wygląda nieco inaczej. W ostatnich trzech rekordach świata zamiast wykonać dwa obliczenia, wykonaliśmy tylko jedno obliczenie przy użyciu najszybszej znanej formuły ( Formuła Chudnovsky'ego ):

Algorytm ten jest znacznie trudniejszy do wdrożenia, ale jest znacznie szybszy niż algorytmy AGM.

Następnie weryfikujemy cyfry binarne za pomocą wzorów BBP do ekstrakcji cyfr .

Ta formuła pozwala obliczyć dowolne cyfry binarne bez obliczania wszystkich cyfr przed nim. Służy więc do weryfikacji ostatnich kilku obliczonych cyfr binarnych. Dlatego jest znacznie szybszy niż pełne obliczenia.

Zaletą tego jest:

1. Potrzebne jest tylko jedno drogie obliczenie.

Wadą jest:

1. Konieczne jest wdrożenie formuły Bailey – Borwein – Plouffe (BBP).
2. Konieczny jest dodatkowy krok w celu weryfikacji konwersji podstawki z binarnej na dziesiętną.

_{Przejrzałem kilka szczegółów na temat tego, dlaczego weryfikacja kilku ostatnich cyfr oznacza, że ​​wszystkie cyfry są poprawne. Łatwo to jednak zauważyć, ponieważ każdy błąd obliczeniowy zostanie przeniesiony do ostatnich cyfr.}

Teraz ten ostatni krok (weryfikacja konwersji) jest właściwie dość ważny. Jeden z poprzednich rekordzistów świata tak naprawdę nas do tego wezwał, ponieważ początkowo nie przedstawiłem wystarczającego opisu jego działania.

Więc wyciągnąłem ten fragment z mojego bloga:

N = # of decimal digits desired
p = 64-bit prime number

Oblicz A za pomocą arytmetyki podstawowej 10, a B za pomocą arytmetyki binarnej.

Jeśli A = B, to z „bardzo wysokim prawdopodobieństwem” konwersja jest prawidłowa.

Więcej informacji można znaleźć na moim blogu Pi - 5 bilionów cyfr .

Bez wątpienia, dla twoich celów (które, jak zakładam, jest tylko ćwiczeniem programistycznym), najlepszą rzeczą jest sprawdzenie twoich wyników względem dowolnej z cyfr cyfry pi w Internecie.

A skąd wiemy, że te wartości są prawidłowe? Cóż, mogę powiedzieć, że istnieją metody informatyczne, aby udowodnić, że implementacja algorytmu jest poprawna.

Bardziej pragmatycznie, jeśli różni ludzie używają różnych algorytmów i wszyscy zgadzają się (wybrać liczbę) tysiąc (milion, cokolwiek) miejsc po przecinku, co powinno dać ci ciepłe, niewyraźne wrażenie, że mają rację.

Historycznie William Shanks opublikował liczbę pi do 707 miejsc po przecinku w 1873 roku. Biedny człowiek, popełnił błąd, zaczynając od 528 miejsca po przecinku.

Co ciekawe, w 1995 r. Opublikowano algorytm, który miał właściwość, która bezpośrednio obliczałaby n-tą cyfrę (podstawa 16) liczby pi bez konieczności obliczania wszystkich poprzednich cyfr !

Wreszcie, mam nadzieję, że twój początkowy algorytm nie był. pi/4 = 1 - 1/3 + 1/5 - 1/7 + ...Być może jest to najprostszy program, ale jest to również jeden z najwolniejszych sposobów. Zapoznaj się z artykułem pi na Wikipedii, aby uzyskać szybsze podejście.

Możesz użyć wielu podejść i sprawdzić, czy są zbieżne z tą samą odpowiedzią. Lub weź trochę z sieci. Algorytm Chudnovsky'ego jest zwykle używany jako bardzo szybka metoda obliczania liczby pi. http://www.craig-wood.com/nick/articles/pi-chudnovsky/

Seria Taylor jest jednym ze sposobów przybliżenia liczby pi. Jak wspomniano, zbiega się powoli.

Częściowe sumy szeregu Taylora można pokazać w granicach pewnego mnożnika następnego terminu od prawdziwej wartości liczby pi.

Inne sposoby przybliżania liczby pi mają podobne sposoby obliczania błędu maksymalnego.

Wiemy o tym, ponieważ możemy to udowodnić matematycznie.

Możesz spróbować obliczyć sin(pi/2)(lub cos(pi/2)zresztą) używając (dość) szybko zbieżnych szeregów mocy dla grzechu i cos. (Jeszcze lepiej: użyj różnych formuł podwójnych, aby obliczyć bliżej, x=0aby uzyskać szybszą konwergencję.)

BTW, lepsze niż używanie serii dla tan(x)jest, przy obliczeniach powiedzmy cos(x)jako czarna skrzynka (np. Możesz użyć serii Taylor jak powyżej) to wyszukiwanie root za pomocą Newtona. Istnieją z pewnością lepsze algorytmy, ale jeśli nie chcesz weryfikować ton cyfr, powinno to wystarczyć (i nie jest to trudne do wdrożenia, a potrzebujesz tylko rachunku różniczkowego, aby zrozumieć, dlaczego to działa).