BBP算法所需的工作精度？

Question

我期待在低內存環境下計算Pi的第 n。由於我沒有小數點，所以這個integer-only BBP algorithm in Python是一個很好的起點。我只需要一次計算Pi的一個數字。 如何確定最低可以設置的D，「工作精度的位數」？

D = 4給了我很多正確的數字，但幾個數字將會被刪除一個。例如，計算數字393的精度爲4給了我0xafda，從中提取數字0xa。但是，正確的數字是0xb。

無論我設置D有多高，似乎測試足夠數量的數字都會找到一個公式返回錯誤值的位置。

我已經嘗試提高精度，當數字「關閉」到另一個，例如0x3fff或0x1000，但找不到任何「關閉」的良好定義;例如，計算數字9798給我0x c de6，它不是非常接近0xd000，但正確的數字是0xd。

任何人都可以幫助我找出需要多少工作精度來計算給定的數字使用此算法？

謝謝

編輯
僅供參考：

 
precision (D) first wrong digit 
------------- ------------------ 
3    27 
4    161 
5    733 
6    4329 
7    21139 
8+    ??? 

請注意，我在時間計算一個數字，如：

for i in range(1,n): 
    D = 3 # or whatever precision I'm testing 
    digit = pi(i) # extracts most significant digit from integer-only BBP result 
    if(digit != HARDCODED_PI[i]): 
     print("non matching digit #%d, got %x instead of %x" % (i,digit,HARDCODED_PI[i])) 

Answer 1

無關於我設定D有多高，似乎是 測試足夠數量的 數字找到一個公式 返回不正確的值。

如果您正在測試足夠數量的數字 - 算法不使用任意精度，您將始終會收到錯誤，因此舍入錯誤最終會顯示出來。

當數字沒有改變時，帶有中斷的無界迭代將很難確定給定位數所需的最小精度。

最好的辦法是根據經驗確定它，理想情況是通過與已知的正確源進行比較，並增加數字精度直到匹配，或者如果正確源不可用，則以您的最大精度開始我猜是14，因爲第15位數字幾乎總是包含舍入誤差。）

編輯：更確切地說，該算法包括一個循環 - 從0..n，其中n是要計算的數字。循環的每次迭代都會引入一定數量的錯誤。循環足夠多的次數後，錯誤將侵入您正在計算的最重要的數字，因此結果將是錯誤的。

維基百科文章使用14位數的精度，這足以正確計算10 ** 8位數。正如您所示，精度較低的數字會導致較早發生的錯誤，因爲精度較低，並且通過較少的迭代就會顯示錯誤。最終的結果是，我們可以正確計算數字的n的值變得更低，精度更低。

如果您有D十六進制數字的精度，那就是D * 4位。每次迭代時，最低有效位引入0.5位的誤差，所以經過2次迭代，LSB有可能出錯。在求和過程中，這些錯誤將被添加，並且累積起來。如果總計的錯誤數達到最高有效位的LSB，那麼您提取的單個數字將是錯誤的。粗略地說，就是當N> 2 **（D-0.75）時。 （正確到一些對數基數。）

經驗地推斷您的數據，似乎近似擬合是N =〜（2 **（2.05 * D）），儘管數據點很少，所以這可能不是一個準確的預測器。

您選擇的BBP算法是迭代的，因此計算序列中數字的時間會更長。要計算數字0..n，將採取步驟O(n^2)。

維基百科的文章給出了一個公式，用於計算不需要迭代的第n位數字，只是指數和有理數。這將不會像迭代算法那樣遭受同樣的精度損失，並且您可以根據需要在常量時間內（或者最壞的對數類型，取決於具有模數的冪運算的實現）計算pi的任何數字，所以計算n數字將花費O(n)時間可能是O（n log n）。