什麼是計算e到2萬億位數的最快方法？

Question

我想計算 e至2兆（2,000,000,000,000）位數。這是大約1.8 TiB的純 e。我剛剛實現了一個使用GMP（code can be found here）的泰勒級數展開算法。

不幸的是，它在我的計算機上總計超過4000個術語時崩潰，可能是因爲它耗盡內存。

計算技術的現狀是什麼 e？哪種算法最快？任何值得關注的開源實現？請不要提及 y-cruncher，它是封閉源代碼。

Answer 1

由於我是您提到的y-cruncher程序的作者，我會添加我的2美分。是

對於這樣一個大的任務，必須解決的兩個最大障礙如下：

1. 內存
2. 運行時間複雜度

內存

2萬億數字是極端 - 至少可以說。這是current record set by Shigeru Kondo and myself back in 2010的兩倍。 （我們花了超過9天的時間用y-cruncher計算1萬億位數。）

以純文本形式表示，大約是十億分之1.8 TiB。在打包的二進制表示中，即773 GiB。

如果您打算對此大小的數字進行算術運算，您將需要773 GiB，對於每個操作數不計算臨時記憶。

可行的是，y-cruncher實際上需要8.76 TiB的內存來做這個計算所有內存。所以你可以期望其他實現需要相同的給定值或最大值爲2。

這就是說，我懷疑你會有足夠的內存。即使你做了，它也會是NUMA。所以替代方案是使用磁盤。但這不是微不足道的，爲了高效率，您需要將內存視爲緩存並對內存和磁盤之間傳輸的所有數據進行微管理。

---

運行時間複雜度

在這裏，我們有其他的問題。對於2萬億位數字，你需要一個非常快速的算法。不只是任何快速算法，而是一個準線性運行時算法。

您目前的嘗試運行在O(N^2)左右。所以即使你有足夠的記憶力，它也不會在你的一生中完成。

的標準方法來計算e爲高精度運行在O(N log(N)^2)和結合了以下算法：

• 上的e泰勒級數展開Binary Splitting。
• FFT-based large multiplication

幸運的是，GMP已經使用基於FFT的大乘法。但它缺少兩個關鍵特性：

1. 在沒有足夠內存時使用磁盤的外核（交換）計算。
2. 它不是並行化的。

第二點並不重要，因爲您可以等待更長的時間。但是，對於所有實際的目的，你可能需要推出自己的。這就是我寫y-cruncher時所做的。

---

儘管如此，還有許多其他的鬆散端也需要被照顧的：

1. 最後部門將需要快速算法像牛頓法。
2. 如果你要用二進制計算，你需要做一個基數轉換。
3. 如果計算需要花費大量時間和大量資源，則可能需要實現容錯來處理硬件故障。

Answer 2

既然你有一個目標，你想要多少位數（2萬億），你可以估計你需要計算e到這個位數所需的條件。由此，您可以估計需要追蹤多少位的精度以避免在第2萬個位置出現舍入誤差。

如果我從斯特林的近似計算得出的結果是正確的，那麼10到2萬億的倒數就是大約1000億因子的倒數。這就是你需要多少條款（100億美元）。不過，這個故事比這個好一點，因爲在這之前，你會開始在計算術語的時候扔掉很多數字。

由於e計算爲反向因子的總和，因此您的所有術語都是有理數的，因此它們可表示爲重複小數。因此，您的術語的小數點擴展將是（a）指數，（b）非重複部分，以及（c）重複部分。如果您以這種方式查看條款，可能會有一些效率可以利用。

無論如何，祝你好運！