算法題：如何判斷計(jì)算的 π 值是否精確？
查看下文之前，大家可以先想想。來看看 π 值計(jì)算世界紀(jì)錄保持者 Mysticial 的回復(fù)。
問題（來自Ishan Sharma）：
我曾試過用各種不同的方法，來做一個(gè)按序輸出顯示 π 值的程序。我試過泰勒級(jí)數(shù)法，但是它收斂地非常慢（這是之后，當(dāng)我將我的結(jié)果和網(wǎng)上的值對(duì)比時(shí)發(fā)現(xiàn)的）。總之，我正試著找出更好的算法。
所以，當(dāng)我在寫這個(gè)程序時(shí)總遇到問題，不管使用什么算法，我都有一個(gè)困惑：我如何才能知道我計(jì)算的數(shù)字是正確的呢？
最高票數(shù)的回答（來自Mysticial）：
由于我是計(jì)算 π 值的世界紀(jì)錄保持者（10 萬億位），我來談一下我的拙見：
除非你是想創(chuàng)造一個(gè)新的世界記錄，否則通常的解決辦法就是對(duì)比已知值驗(yàn)證計(jì)算值。所以，這很簡(jiǎn)單。
其實(shí)，我就有一個(gè)列出了數(shù)字片段的網(wǎng)頁(yè)。它就是為了驗(yàn)證計(jì)算值。http://www.numberworld.org/digits/Pi/
但是，當(dāng)你進(jìn)入世界記錄的范圍，就沒有已知值讓你對(duì)比驗(yàn)證了。
通常，驗(yàn)證計(jì)算值的標(biāo)準(zhǔn)方法是用另一種算法再計(jì)算一次。所以，只要有一個(gè)計(jì)算錯(cuò)誤，數(shù)字就不會(huì)相同。
這經(jīng)常會(huì)花兩倍多的時(shí)間（因?yàn)榈诙N算法一般會(huì)慢一點(diǎn)）。但這是驗(yàn)證計(jì)算值的唯一方法，只要你涉及了從沒被計(jì)算過的未知領(lǐng)域或是一個(gè)新的世界記錄，就只能這么做。
在超級(jí)計(jì)算機(jī)保持世界記錄的時(shí)候，有兩種不同的常見AGM算法：
它們都是時(shí)間復(fù)雜度為 O(N log(N)^2) 的算法，而且相當(dāng)簡(jiǎn)單。但是，如今的算法有些不同了。在最近的3個(gè)世界記錄中，我們只通過最快的公式（Chudnovsky 公式）進(jìn)行一次運(yùn)算，而不是兩次。
這個(gè)算法比較難，但是它比AGM算法快很多。
然后我們用BBP公式進(jìn)行數(shù)字提取，來驗(yàn)證這個(gè)二進(jìn)制數(shù)字。
使用這個(gè)公式，你可以計(jì)算任何二進(jìn)制數(shù)字，并且不用計(jì)算它之前的所有數(shù)字。因此，它用來驗(yàn)證最后少數(shù)的二進(jìn)制計(jì)算值。所以，它比一個(gè)完整的計(jì)算要快得多。
它的優(yōu)點(diǎn)是：
1.只需要進(jìn)行一次復(fù)雜的運(yùn)算。
它的缺點(diǎn)是：
- 需要實(shí)現(xiàn)Bailey–Borwein–Plouffe (BBP)公式。
- 需要多一步來驗(yàn)證：基數(shù)從二進(jìn)制到十進(jìn)制的轉(zhuǎn)換。
我曾列出過一些細(xì)節(jié)來說明為什么驗(yàn)證最后幾個(gè)數(shù)字就能證明所有數(shù)字都是正確的。但這是顯而易見的，因?yàn)槿魏斡?jì)算錯(cuò)誤都會(huì)傳遞到最后一個(gè)數(shù)字。
現(xiàn)在，最后一步（驗(yàn)證轉(zhuǎn)換）實(shí)際上是非常重要的。一位前世界紀(jì)錄保持者曾呼吁我們不要這么做，因?yàn)椋乙婚_始并沒有給出它詳細(xì)的過程。
所以，現(xiàn)在我把我博客的這個(gè)片段貼出來：
N = #所需的小數(shù)位數(shù)
p = 64位素?cái)?shù)
用10進(jìn)制算法計(jì)算A，用二進(jìn)制算法算B。
如果 A=B，那么由于“極大可能性”，轉(zhuǎn)換是正確的。
深入閱讀，可查看我的這篇博文《Pi – 5 萬億位》。
原文鏈接： Stack Overflow 翻譯： 伯樂在線 - colleen__chen
