Jaki jest najszybszy sposób obliczenia e do 2 trylionów cyfr?

Question

Chcę obliczyć e na 2 tryliony (2 000 000 000 000) cyfr. To około 1,8 TiB czystego e. Właśnie zaimplementowałem algorytm rozwijania serii taylor przy użyciu GMP (code can be found here).

Unfortuanetly to zawiesza się podczas sumowania ponad 4000 warunków na moim komputerze, prawdopodobnie dlatego, że zabrakło mu pamięci.

Jaki jest obecny stan wiedzy w dziedzinie komputerów e? Który algorytm jest najszybszy? Jakieś implementacje open source, na które warto zwrócić uwagę? Proszę nie wspominać o y-cruncher, to zamknięte źródło.

Answer 1

Ponieważ jestem autorem programu y-cruncher, o którym wspomniałeś, dodam moje 2 centy.

Dla takiego dużego zadania, dwie największe przeszkody, które muszą zostać poruszone są następujące:

1. pamięci
2. Run-time Złożoność

pamięci

2 bilion cyfr to ekstremalnie - co najmniej. To dwa razy więcej niż current record set by Shigeru Kondo and myself back in 2010. (Zajęło nam to ponad 9 dni na wyliczenie 1 tryliona cyfr za pomocą y-crunchera).

W tekście zwykłym, to około 1,8 TiB w systemie dziesiętnym. W spakowanej reprezentacji binarnej to 773 GiB.

Jeśli zamierzasz wykonywać operacje arytmetyczne na liczbach tej wielkości, będziesz potrzebować 773 GiB dla każdego operandu nie licząc pamięci scratch.

Możliwe, że Y-cruncher potrzebuje 8.76 TiB pamięci, aby wykonać to obliczenie wszystkie w pamięci RAM. Można więc oczekiwać, że inne implementacje będą wymagały tego samego lub przynajmniej przyjmą współczynnik 2.

Powiedziałem, że wątpię, że będziesz miał dość barana. A nawet gdybyś tak zrobił, byłby to zdecydowanie NUMA. Alternatywą jest użycie dysku. Ale to nie jest trywialne, aby być wydajnym, trzeba traktować pamięć jako pamięć podręczną i przenosić wszystkie dane przesyłane między pamięcią a dyskiem.

---

Run-time Złożoność

Tutaj mamy inny problem. Dla 2 trylionów cyfr potrzebny będzie bardzo szybki algorytm. Nie tylko jakikolwiek szybki algorytm, ale quasi-liniowy algorytm wykonawczy.

Twoja obecna próba trwa około O(N^2). Więc nawet jeśli masz dość pamięci, nie skończy się to za twojego życia.

Standardowe podejście do obliczania e wysokiej precyzji przebiega O(N log(N)^2) łącząc następujące algorytmy:

• Binary Splitting na rozbudowę szereg Taylora e.
• FFT-based large multiplication

szczęście GMP już używa FFT oparte dużą mnożenia. Ale nie ma dwóch ważnych funkcji:

1. Obliczenia na dysku (zamiana) na użycie dysku, gdy brakuje pamięci.
2. Nie jest zsynchronizowany.

Drugi punkt nie jest tak ważny, ponieważ można po prostu dłużej czekać. Ale ze względów praktycznych prawdopodobnie będziesz musiał wdrożyć własne. I to właśnie zrobiłem, gdy pisałem y-crunchera.

---

Powiedział, że istnieje wiele innych luźne końce, które również muszą być załatwione:

1. The końcowego podziału wymagać będzie szybki algorytm jak metoda Newtona.
2. Jeśli chcesz obliczyć w systemie dwójkowym, będziesz musiał wykonać konwersję podstawową.
3. Jeśli obliczenia zajmie dużo czasu i dużo zasobów, być może trzeba będzie wprowadzić tolerancję błędów w celu obsługi awarii sprzętu.

Answer 2

Ponieważ masz cel, ile cyfr chcesz (2 tryliony), możesz oszacować, ile wyrażeń musisz obliczyć, aby obliczyć e na taką liczbę cyfr. Z tego można oszacować, ile dodatkowych cyfr precyzji będziesz potrzebował, aby śledzić, aby uniknąć błędów zaokrąglania w 2 trylionowym miejscu.

Jeśli moje obliczenia z przybliżenia Stirlinga są poprawne, wzajemność od 10 do 2 trylionów dotyczy odwrotności 100 miliardów silni. A więc chodzi o to, ile słów będziesz potrzebować (100 miliardów). Ta historia jest trochę lepsza, ponieważ zaczniesz wyrzucać wiele liczb w obliczeniach terminów na długo przed tym.

Ponieważ e jest obliczany jako suma odwrotnych silni, wszystkie terminy są racjonalne, a zatem można je wyrazić jako powtarzające się miejsca dziesiętne. Zatem dziesiętna ekspansja twoich warunków będzie (a) wykładnikiem, (b) nie powtarzającą się częścią, (c) powtarzającą się częścią. Może być trochę korzyści, które możesz wykorzystać, jeśli spojrzysz na warunki w ten sposób.

W każdym razie powodzenia!