algorithm - pseudocode是什麼 - 我如何確定我的pi計算是否準確?




pseudo code or (4)

你可以使用多種方法,看看他們是否收斂到相同的答案。 或者從網上搶一些。 Chudnovsky算法通常用作計算pi的非常快速的方法。 http://www.craig-wood.com/nick/articles/pi-chudnovsky/

我正在嘗試各種方法來實現一個順序給出pi數字的程序。 我嘗試了泰勒級數的方法,但它證明收斂速度非常緩慢(在一段時間後我將結果與在線值進行比較時)。 無論如何,我正在嘗試更好的算法。

所以,在編寫程序時,我遇到了一個問題,就像所有的算法一樣:我怎麼知道我計算的n數字是準確的?


你可以用(相當)快速收斂的sin和cos冪級數來計算sin(pi/2) (或cos(pi/2) 。 (甚至更好:使用各種加倍公式來計算更近的x=0以獲得更快的收斂。)

順便說一句,比使用tan(x)系列更好的是,將計算稱為cos(x)作為黑盒子(例如,您可以使用泰勒系列)就是通過牛頓進行根發現。 當然有更好的算法,但是如果你不想驗證大量的數字,這應該就足夠了(並且這不是很棘手的實現,你只需要一點微積分來理解它的工作原理。)


泰勒級數是逼近pi的一種方法。 如前所述,它收斂緩慢。

泰勒級數的部分和可以顯示在下一項的某個乘數之內,遠離pi的真實值。

其他逼近pi的方法也有類似的方法來計算最大誤差。

我們知道這是因為我們可以用數學來證明它。


由於我是目前pi數最多的世界紀錄保持者,因此我會補充我的兩分錢

除非你真的設定了一個新的世界記錄,否則通常的做法就是根據已知值驗證計算的數字。 這很簡單。

事實上,我有一個網頁列出了數字片段,用於驗證對他們的計算: http://www.numberworld.org/digits/Pi/ : http://www.numberworld.org/digits/Pi/

但是當你進入世界紀錄的領域時,沒有什麼可比的。

歷史上,驗證計算數字是否正確的標準方法是使用第二種算法重新計算數字。 所以如果任何一個計算結果不好,最後的數字將不匹配。

這通常是所需時間的兩倍以上(因為第二種算法通常較慢)。 但是,一旦你走進未曾計算的數字和新的世界紀錄的未知領域,這是驗證計算數字的唯一方法。

回到超級計算機設置記錄的日子,通常使用兩種不同的AGM算法

這些都是O(N log(N)^2)算法,相當容易實現。

但是,現在,情況有些不同。 在最近的三次世界記錄中,我們不是執行兩次計算,而是使用已知公式最快的公式( Chudnovsky公式 )進行一次計算:

該算法實施起來要困難得多,但它比AGM算法快得多。

然後我們使用BBP公式來驗證數字提取的二進制數字。

該公式允許您計算任意二進制數字, 而不必計算它之前的所有數字。 所以它被用來驗證最後幾個計算的二進制數字。 因此它比完整的計算速度快得多。

這樣做的好處是:

  1. 只需要一個昂貴的計算。

缺點是:

  1. 需要Bailey-Borwein-Plouffe (BBP)公式的實現。
  2. 需要額外的步驟來驗證從二進製到十進制的基數轉換。

我已經詳細說明了為什麼驗證最後幾位意味著所有數字都是正確的。 但很容易看到這一點,因為任何計算錯誤都會傳播到最後的數字。

現在最後一步(驗證轉換)實際上相當重要。 之前的世界紀錄保持者之一實際上就此向我們發出了邀請 ,因為最初,我沒有給出足夠的關於它如何工作的描述。

所以我從我的博客中拉出了這個片段:

N = # of decimal digits desired
p = 64-bit prime number

使用二進制算法計算使用base 10算法和B。

如果A = B ,那麼以“非常高的概率”,轉換是正確的。

要進一步閱讀,請參閱我的博客文章Pi - 5 Trillion Digits







pi