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

772

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?

Ishan Sharma
źródło
20
bardziej problem matematyczny. dobre algorytmy dają również oszacowanie błędu.
przykład
35
Porównaj z pi?
Dave Newton
55
@chris: „dosłownie wszędzie”?
Wyścigi lekkości na orbicie
32
Mogę sprawdzić dla ciebie do 3.141592653589793238462643383279502, poza tym, dlaczego potrzebujesz tak dużej liczby cyfr? (To coś w rodzaju dokładności poziomu atomowego z okręgiem wielkości wszechświata.)
AJ Henderson
65
Dlaczego po prostu nie podzielisz liczby przez pi i nie sprawdzisz, czy wynik to 1? (tylko żartuję)
user541686

Odpowiedzi:

1628

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 :

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 ):

Wpisz opis zdjęcia tutaj

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 .

Wpisz opis zdjęcia tutaj

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

Wpisz opis zdjęcia tutaj

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

Wpisz opis zdjęcia tutaj

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 .

Tajemniczy
źródło
15
I aby odpowiedzieć na inne pytanie, w jaki sposób wiedzieć, kiedy konkretny algorytm jest zbieżny z cyframi N: Wymaga to znajomości zachowania algorytmu w zakresie zbieżności. Seria Taylora ArcTan(1)jest logarytmicznie zbieżna. Potrzebujesz więc wykładniczo dużej liczby terminów, aby się zjednoczyć - krótko mówiąc, nie używaj go.
Mysticial
21
Tak, formuła Chudnovsky'ego zbiega się ze stałą 14,18 cyfr na termin. Możesz więc podzielić całkowitą liczbę cyfr, aby uzyskać liczbę potrzebnych terminów. (Dokładna wartość jest: Log(151931373056000)/Log(10) = 14.181647462725477655...)
Mysticial
7
@ erikb85 Kinda. Formuła BBP (do pewnego stopnia) liczy się jako drugi algorytm. Ale samo w sobie nie wystarczy, ponieważ nie weryfikuje konwersji do podstawy 10. Pomysł użycia sprawdzania konwersji BBP + w celu wyeliminowania potrzeby drugiego obliczenia nie był mój. Po raz pierwszy zrobił to Fabrice Bellard w swoim rekordzie świata w 2009 roku. To był tak dobry pomysł, że zrobiliśmy to samo i ulepszyliśmy to.
Tajemniczy
83
@FssukWangadu Mogę mówić tylko za siebie, ale proszę bardzo: nigdy tak naprawdę nie dbałem o samego Pi. Dla mnie to tylko kolejny numer. Wartość nie jest w samej liczbie ani w 10 terabajtach bezużytecznych cyfr, są to metody, które są używane do jej osiągnięcia. Stulecia matematyki i dziesięciolecia badań komputerowych / programistycznych, które przyczyniły się do tego wyczynu, mają zastosowanie w wielu innych dziedzinach, a tym samym są O wiele cenniejsze niż twardy dysk z cyframi. Krótko mówiąc: obliczanie cyfr Pi jest bardziej sportem.
Tajemniczy
8
@ Mistyczne, natknąłem się na twoją stronę obliczeniową Pi z innego pytania o przepełnienie stosu i nie mogłem powstrzymać się od gapienia się i chichotania z powodu tego, co zrobiliście. Uwielbiałem awarie dysków twardych / trzęsienia ziemi w logach :) po prostu niesamowite!
Joe
48

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.

Larry Smith
źródło
7
Ta ostatnia formuła (formuła Leibniza, iirc) faktycznie naprzemiennie dodaje i odejmuje.
Thomas
21

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/

argentage
źródło
Zmniejsza szanse, ale wciąż nie mogę być pewien rozwiązania z wieloma podejściami, co jeśli oba są błędne. Sprawdzanie w sieci nie jest ważne, więc dlaczego nie usunąć wartości z samej sieci. Mam na myśli bbp, który jest bardziej odpowiedni?
Ishan Sharma
7
@IshanSharma Jeśli oba algorytmy są niezależne, prawdopodobieństwo, że oba obliczenia są błędne z identycznymi wynikami, jest prawie zerowe. Jeśli coś pójdzie nie tak w obu obliczeniach, końcowe wyniki nie będą pasować - więc wiesz, że przynajmniej jeden z nich jest nieprawidłowy.
Mysticial
15

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.

Jak - Adam Nevraumont
źródło
Oddelegowany. Myślę, że większość odpowiedzi tutaj nie przykłada wystarczającej wagi do koncepcji dowodu matematycznego . Cokolwiek twój program służy do obliczania cyfr liczby pi, nigdy nie będzie bardziej przekonujący niż najbardziej przekonujący matematyczny dowód, że metoda twojego programu faktycznie oblicza liczbę pi. Co sugeruje inne ograniczenie dla programów, które pi obliczają pi: że powinny mieć na celu zarówno zrozumiałość, jak wydajność i poprawność.
Luis Casillas
5

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).

użytkownik1974703
źródło
6
Nie bardzo rozumiem, jak to pomogłoby zauważyć, że 1000-ta cyfra jest wyłączona o 1. Potrzebujesz bardzo dokładnych wartości sin(pi/2), prawda?
Matthieu M.
Nie jestem pewien, co powiedzieć o poprzedniej odpowiedzi, chyba że jest to żart czy coś takiego. sin (pi / 2) = 1 cos (pi / 2) = 0 Powiedziałbym, że te z pewnością szybko się zbiegają.
BentFranklin 20.01.2013
15
Myślę, że nie jest oczywiste dla wszystkich, że ocena sin(x)i cos(x)wysoka precyzja są w rzeczywistości o wiele trudniejsze niż samo obliczenie Pi.
Mysticial
2
Z oczywistych powodów nie powinieneś używać do tego sin (pi / 2). Lepiej zamiast tego użyj sin (pi / 6) i upewnij się, że wyjdzie dokładnie jako 1/2.
Robert Lozyniak,