那些打破圓周率小數位計算的記錄是怎麼判斷計算得正不正確的？

01-25

現在的很多記錄是由計算機創造的，那怎麼判斷計算機計算得正不正確？

在BBP演算法發現以前,想要驗算別人的結果除非你也計算到那個位數.然後驗算哈希或者直接對比.

不過我們現在有了天才的發現------BBP演算法.

BBP演算法能跳過前面的位數直接計算目標位數,對別人的結果作大量隨機檢驗都通過的話就可以認為別人的結果正確...

因為計算一般數學上是沒問題的,有問題的一般是硬體和演算法.硬體有毛病或者演算法各種溢出越界,並行兩個問題了有.

這兩種錯誤都是一錯基本接下去全是錯的. 級數法(Chudnovsky 公式)還好,使用 AGM 迭代演算法的話就白算了.

=============================================================

下面介紹BBP演算法:

BBP公式全稱為 貝利-波爾溫-普勞夫公式 (Bailey–Borwein–Plouffe formula),該公式發現於1995年,以三位發表者的名字命名.

最初的一個BBP公式是:

$[pi = sumlimits_{k = 0}^infty {frac{1}{{{{16}^k}}}left( {frac{4}{{8k + 1}} - frac{2}{{8k + 4}} - frac{1}{{8k + 5}} - frac{1}{{8k + 6}}} ight)} ]$

證明:https://pic2.zhimg.com/v2-050d93c0e8e8a55ed3ce1458b7473315_b.png

BBP類演算法(BBP-Type Algorithm)就是形如 $displaystyle {alpha =sum _{k=0}^{infty }left[{frac {1}{b^{k}}}{frac {p(k)}{q(k)}} ight]}$ 的一類公式,其中 $alpha$ 是目標常數,p,q是整係數多項式,b表示移位用的進位.

因為這個形式,所以我們可以採用 Bailey-P記號 來表示一個BBP公式.

所以上面這個公式就能記為:

BBP公式本身收斂遠遠慢於拉馬努金類公式

直接計算級數值不叫BBP演算法.

BBP演算法能跳過前面的位數直接計算目標位數,其優越性在於能夠分散式計算.

其原理其實並不複雜,以 $pi$ 的計算為例.

兩邊乘以 $16^n$ 來跳過n個16進位,相當於十進位中的乘10小數點右移一位.

$[egin{aligned} pi = sum_{k = 0}^{infty} frac{1}{16^k} left( frac{4}{8k + 1} - frac{2}{8k + 4} - frac{1}{8k + 5} - frac{1}{8k + 6} ight)\ 16^{n} pi = sum_{k = 0}^{infty} left( frac{4 cdot 16^{k-n}}{8k + 1} - frac{2cdot 16^{k-n}}{8k + 4} - frac{ 16^{k-n}}{8k + 5} - frac{16^{k-n}}{8k + 6} ight) end{aligned} ]$

兩邊取小數部分,如果需要的位數比較多可以 $mod 1,$ 然後使用快速冪模加速.

$[egin{aligned} { {16^n}pi } = left{ {sumlimits_{k = 0}^infty {left( {frac{{4 cdot {{16}^{k - n}}}}{{8k + 1}} - frac{{2 cdot {{16}^{k - n}}}}{{8k + 4}} - frac{{{{16}^{k - n}}}}{{8k + 5}} - frac{{{{16}^{k - n}}}}{{8k + 6}}} ight)} } ight}\ = { 4{ {16^n}{S_1}} - 2{ {16^n}{S_4}} - { {16^n}{S_5}} - { {16^n}{S_6}} } \ { {16^n}{S_j}} = left{ {left{ {sumlimits_{k = 0}^n {frac{{{{16}^{n - k}}}}{{8k + j}}} } ight} + sumlimits_{k = n + 1}^infty {frac{{{{16}^{n - k}}}}{{8k + j}}} } ight}\ = left{ {left{ {sumlimits_{k = 0}^n {frac{{{{16}^{n - k}}quad mod ,8k + j}}{{8k + j}}} } ight} + sumlimits_{k = n + 1}^infty {frac{{{{16}^{n - k}}}}{{8k + j}}} } ight}\ end{aligned} ]$

一般對於相應的 $b,n$ 值,係數線性相關.

$n=8$ 時一般化的公式長成這個樣子:

$[pi = sumlimits_{k = 0}^infty {{{left( {frac{1}{{16}}} ight)}^k}} left( {frac{{8r + 4}}{{8k + 1}} - frac{{8r}}{{8k + 2}} - frac{{4r}}{{8k + 3}} - frac{{8r + 2}}{{8k + 4}} - frac{{2r + 1}}{{8k + 5}} - frac{{2r + 1}}{{8k + 6}} + frac{r}{{8k + 7}}} ight)]$

最初的BBP公式靠猜發現,BBP公式的原理現在並不是完全清楚,BBP公式並不能用來計算如 $e,gamma$ 這樣的其他數學常數.

大量的BBP公式靠PSLQ演算法發現,也就是整數關係偵查演算法,說白了就是研究如何猜的演算法...

由此促進了一門研究猜公式的學科的發展------實驗數學(Experimental Mathematics)...

倘若拉馬努金在世一定能為這個學科做出重大貢獻,要在茫茫沙海中淘到金子非強大的數學直覺不能做到...

理論方面,一些BBP公式來源於黎曼Zeta函數、多對數函數Li和反正切函數.由於 $zeta$ 函數和 $pi$ 的關係使得這種式子在特定的時候能用來計算圓周率 $pi$ 和卡特蘭常數G.

公式中取 $s=p$ 時總能表示出 $zeta(p)$ ,有數學家相信這能揭示 $zeta(3)$ 與 $pi^3$ 的深層關係.

反餘切函數和對數函數能比較容易的用P記號展開.

$[egin{aligned} operatorname{arccot} b = arctan {frac {1}{b}}\ ={frac {1}{b}}-{frac {1}{b^{3}3}}+{frac {1}{b^{5}5}}-{frac {1}{b^{7}7}}+{frac {1}{b^{9}9}}+cdots \ =sum _{k=1}^{infty }left[{frac {1}{b^{k}}}{frac {sin {frac {kpi }{2}}}{k}} ight]\ ={frac {1}{b}}sum _{k=0}^{infty }left[{frac {1}{b^{4k}}}left({frac {1}{4k+1}}+{frac {-b^{-2}}{4k+3}} ight) ight]\ ={frac {1}{b}}Pleft(1,b^{4},4,(1,0,-b^{-2},0) ight)\ ln left( {1 - frac{1}{{{b^m}}}} ight) = - frac{1}{{{b^m}}}sumlimits_{k = 0}^infty {frac{1}{{1 + k}}{b^{ - mk}}} \ = - frac{1}{{{b^m}}}P(1,{b^m},1,(1))\ end{aligned}]$

另外進位b只要不等於1就行了,等於小數那是無所謂的...比如黃金分割進位中表示$pi$.

$[{pi ^2} = sumlimits_{k = 0}^infty {frac{1}{{{phi ^{5k}}}}left( {frac{{{phi ^{ - 2}}}}{{{{left( {5k + 1} ight)}^2}}} - frac{{{phi ^{ - 1}}}}{{{{left( {5k + 2} ight)}^2}}} - frac{{{phi ^{ - 2}}}}{{{{left( {5k + 3} ight)}^2}}} + frac{{{phi ^{ - 5}}}}{{{{left( {5k + 4} ight)}^2}}} + frac{{2{phi ^{ - 5}}}}{{{{left( {5k + 5} ight)}^2}}}} ight)} ]$

這裡 $displaystyle {phi = frac{1}{2}left( {sqrt 5 + 1} ight)}$ ,不是0.618...

另外附上我發現的可能是最短的計算 $pi$ 的BBP公式:

$[sumlimits_{k = 0}^infty {frac{{{{( - 1)}^k}}}{{{4^k}}}left( {frac{2}{{4k + 1}} + frac{2}{{4k + 2}} + frac{1}{{4k + 3}}} ight)} ]$

None of the answers proposed so far really answered the question. So this is my short answer:

Bailey

For a detailed answer given by the world-record holder, see here:

http://stackoverflow.com/questions/14283270/how-to-determine-whether-my-calculation-of-pi-is-accurate/14283481#14283481

無需專門判斷，只需監管CPU的運行即可。

生產實踐幾乎不會用到小數點後十位，算十億位的目的本來就不是圓周率，而是演算法與硬體可靠性。

一定要檢查的話，就等下一次別人算到同樣地方核對。

這問題問的有一定意義，近代數學裡產生一門新的學科，就是研究怎樣讓計算機證明數學定理，這和以前計算機參與數學計算完全不同，因為以前人們只是讓計算機做可以預見的事，現在是讓計算機做連人類自己都不知道該咋做的事。

然後無論怎樣，這研究成功了，據說當年第一次獨立證出四色定理的時候也是小轟動一把，但這個是人類已經證出來的，人們會質疑，到底是計算機證出的？還是你們開了後門作弊證出來的？所以數學家們還是不滿意。

然後又過了一段時間，這次是真的成功了，計算機證明出了費馬大定理，而且這定理人類還沒證明出來。這下就算是外行也挑不出什麼骨頭了。

但重點來了，話雖這樣說，其實數學家們還是有點心虛的，因為計算機的證明過程，非常難懂。

不僅證明過程難懂，演算法也難懂，計算機用來證明定理的程序源代碼也超級複雜，據說有幾十萬行代碼，能從頭到尾看完，看懂代碼的人都不多，誰也不敢保證裡面是不是有bug。

於是又有人質疑了，你怎麼保證說這就是計算機證明出來的？畢竟這代碼只有非常牛逼的人才能看懂，而非常牛逼的人說代碼是沒問題的，所以代碼運行出來的結果也沒問題——這邏輯鏈讓誰看都有點心虛吧？

所以至今還是有點非主流的數學家在反對這個事情，因為它確實有點爭議，當然爭議也不大，大家還是公認費馬大定理是被計算機成功證明出來了的。

那麼說這個事情，是想說人們是如何驗證計算機對於複雜工作的結果是否正確的，基本來說就沒有捷徑，就是讀演算法，讀源碼，如果演算法和源代碼都挑不出毛病，那麼就認為結果也是正確的。只能這樣了。

其實，計算機就算是算錯了，也沒什麼大不了的，當年計算機還沒出現的時候，數學家們把計算圓周率小數點後多少位當成一種競賽，有個人曾經成功保持了很久的記錄，但很多年過去之後，才有人發現，他的計算結果從某一位之後都是錯的。計算機自動定理證明也一樣，有人也曾經宣稱過計算機證出了四色，但後來又被挑出了bug。但是圓周率的演算法是非常簡單的，源代碼也不難，所以計算機算圓周率這種小事，人們還是可以信任的。

==========

@KY Wang

大費定理不是懷爾斯在95年左右寫了幾百頁證明的么，還拿了菲爾茲獎。

匿名用戶給出了圓周率的計算機演算法公式，BBP公式，這裡是中文維基頁面，我也很漲姿勢。

http://zh.wikipedia.org/wiki/%E8%B4%9D%E5%88%A9-%E6%B3%A2%E5%B0%94%E6%B8%A9-%E6%99%AE%E5%8A%B3%E5%A4%AB%E5%85%AC%E5%BC%8F

個人覺得只要能證明演算法是正確的即可，一般而言這裡都是用歸納假設就可以證明了

計算機可以編程序計算圓周率的，並且有很多級數收斂和圓周率有關

看著公式似乎不算很高深，但就是不明白怎麼做到直接就能算出pi的小數點後任意一位數。