算法題：如何判斷計算的 π 值是否精確？

jopen 10年前發布 | 8K 次閱讀算法

國外有位程序員童鞋想做一個輸出 π 值的程序，嘗試過很多種算法。不過不管用哪種算法，他最后都有一個困惑：如何才能確定計算的 π 值是正確的呢？

查看下文之前，大家可以先想想。來看看 π 值計算世界紀錄保持者 Mysticial 的回復。

問題（來自 Ishan Sharma）：

我曾試過用各種不同的方法，來做一個按序輸出顯示 π 值的程序。我試過泰勒級數法，但是它收斂地非常慢（這是之后，當我將我的結果和網上的值對比時發現的）。總之，我正試著找出更好的算法。

所以，當我在寫這個程序時總遇到問題，不管使用什么算法，我都有一個困惑：我如何才能知道我計算的數字是正確的呢？

由于我是計算 π 值的世界紀錄保持者（10 萬億位），我來談一下我的拙見：

除非你是想創造一個新的世界記錄，否則通常的解決辦法就是對比已知值驗證計算值。所以，這很簡單。

其實，我就有一個列出了數字片段的網頁。它就是為了驗證計算值。http://www.numberworld.org/digits/Pi/

但是，當你進入世界記錄的范圍，就沒有已知值讓你對比驗證了。

通常，驗證計算值的標準方法是用另一種算法再計算一次。所以，只要有一個計算錯誤，數字就不會相同。

這經常會花兩倍多的時間（因為第二種算法一般會慢一點）。但這是驗證計算值的唯一方法，只要你涉及了從沒被計算過的未知領域或是一個新的世界記錄，就只能這么做。

在超級計算機保持世界記錄的時候，有兩種不同的常見 AGM 算法：

它們都是時間復雜度為 O(N log (N)^2) 的算法，而且相當簡單。但是，如今的算法有些不同了。在最近的 3 個世界記錄中，我們只通過最快的公式（Chudnovsky 公式）進行一次運算，而不是兩次。

這個算法比較難，但是它比 AGM 算法快很多。

然后我們用 BBP 公式進行數字提取，來驗證這個二進制數字。

使用這個公式，你可以計算任何二進制數字，并且不用計算它之前的所有數字。因此，它用來驗證最后少數的二進制計算值。所以，它比一個完整的計算要快得多。

它的優點是：

1. 只需要進行一次復雜的運算。

它的缺點是：

我曾列出過一些細節來說明為什么驗證最后幾個數字就能證明所有數字都是正確的。但這是顯而易見的，因為任何計算錯誤都會傳遞到最后一個數字。