1樓：匿名使用者
第一類演算法：arctan 的級數
pi/4 = 4 arctan(1/5) - arctan(1/239) (1)
arctan(x) = x - x3/3 + x5/5 - x7/7 + .... (2)
很容易想到，要得到超高精度的 pi 值，實數在計算機中必須以陣列的形式進行存取，陣列的大小跟所需的有效位數成正比。在這個演算法中，pi 的有效位數 n 隨 (2) 的求和項數線性增加。而為計算 (2) 中的每一項，需要進行超高精度實數除以小整數(52, 2392, 2k+1)的迴圈，迴圈所需次數也跟 n 成正比。
所以，這個演算法總的時間複雜度為 o(n2)。
這個演算法的優點是簡單，而且只需要進行整數運算。下面給出我寫的算 pi 程式。在程式中，我採用了一些提高速度的措施：
超高精度實數以陣列的形式進行存取，陣列元素的型別為 64 位整數(long long)，每個元素儲存 12 個十進位制位；對 xk (x = 1/5, 1/239) 的頭部和尾部的 0 的數量進行估計，只對非 0 的部分進行計算。
pi.cpp c++ 源程式，在 linux 下以 g++ pi.cpp -o pi -o2 編譯
pi.s 在 g++ 生成的彙編程式的基礎上進行修改，速度更快，在 linux 下以 g++ pi.s -o pi 編譯
另外，還有許多跟 (1) 類似的式子，但不常用。例如：
pi/4 = arctan(1/2) + arctan(1/3)
pi/4 = 8 arctan(1/10) - arctan(1/239) - 4 arctan(1/515)
第二類演算法：與 1/pi 有關的級數
1/pi = (sqrt(8) / 9801) sumk=0~inf (ramanujan)
1/pi = (sqrt(10005) / 4270934400) sumk=0~inf (chudnovsky)
以上兩個級數(還有其它類似形式的級數，但不常用)比起 arctan 的泰勒級數要複雜得多。雖然仍然是線性收斂，總的時間複雜度也仍然是 o(n2)，但它們的收斂速度相當快， (ramanujan) 每項可以增加 8 位有效數字， (chudnovsky) 每項可以增加 14 位。
在這個演算法中，除了要進行超高精度實數(陣列形式)和小整數的運算外，還有一次超高精度實數的開方和倒數的運算，這需要用到 fft(快速傅立葉變換)，在下文敘述。
第三類演算法：算術幾何平均值和迭代法
算術幾何平均值(arithmetic-geometric mean, agm) m(a, b) 定義如下：
a0 = a, b0 = b
ak = (ak-1 + bk-1) / 2, bk = sqrt(ak-1 bk-1)
m(a, b) = limk->inf ak = limk->inf bk
然後，由橢圓積分的一系列理論(抱歉，過程我不懂)可以推匯出如下公式：
a0 = 1, b0 = 1 / sqrt(2)
1/pi = / 2m(a0, b0)2 (agm)
根據這條公式可以制定適當的迭代演算法。在迭代過程中，有效位數隨迭代次數按 2 的指數增加，即每迭代一次有效位數乘 2。演算法中的超高精度實數的乘、除、開方等運算需要使用 fft，在下文敘述。
綜合考慮 fft 的時間複雜度，整個演算法的時間複雜度約為 o(n log(n)2)。
除了 (agm) 以外，還有其它的迭代序列，它們具有同樣的時間複雜度。例如下面的這個序列將按 4 的指數收斂到 1/pi：
y0 = sqrt(2) - 1, a0 = 6 - 4 sqrt(2)
yk = [1 - sqrt(sqrt(1 - yk-14))] / [1 + sqrt(sqrt(1 - yk-14))], ak = (1 + yk)4 ak-1 - 22k+1 yk (1 + yk + yk2)
1/pi = limk->inf ak (borwein)
fft如上所述，第二和第三類演算法不可避免地要涉及超高精度實數(陣列形式存取的多位數)的乘、除、開方等運算。多位數乘法如果按照常規方法來計算，逐位相乘然後相加，其時間複雜度將達到 o(n2)。使用 fft 可大大減少計算量。
設有複數陣列 a[k] 和 b[k] (k=0~n-1)，正向和反向的離散傅立葉變換(dft)定義如下： (i = sqrt(-1))
b = fftforward(a) : b[k] = sumj=0~n-1 ( a[j] e-i*j*2pi*k/n ) (3)
b = fftbackward(a) : b[k] = (1/n) sumj=0~n-1 ( a[j] ei*j*2pi*k/n ) (4)
(3) 和 (4) 中的 (1/n) 可以放在任何一個式子中，也可以拆成 (1/sqrt(n)) 同時放在兩個式子中，目的是保證正向和反向傅立葉變換以後不會相差一個因子。
當 n 的所有素因子均為小整數，尤其是當 n 為 2 的整數次冪的時候，使用適當的演算法經過仔細的協調，可以避免多餘的計算，使離散傅立葉變換 (3) 和 (4) 減少至 o(n log(n)) 的時間複雜度，即所謂的快速傅立葉變換(fft)。具體的細節請查閱相關書籍。下面給出我寫的一段 fft 程式，僅供參考。
另外也有已經開發的 fft 函式庫，例如 fftw ，可以直接使用。
fft.cpp fft 的 c++ 源程式
利用 fft，要計算 n1 位和 n2 位的兩個多位數乘法，可以這樣進行：開闢兩個長度為 n(n>=n1+n2，取 2m 最佳) 的複數陣列，將兩個多位數從低位到高位分別填入，高位補 0。對兩個陣列分別進行正向傅立葉變換。
將得到的兩個變換後的陣列的對應項相乘，然後進行反向傅立葉變換，最後得到一個結果陣列。由於傅立葉變換是在複數域中進行的，因此還要對結果陣列進行取整和進位，才能得到最終的乘積。
值得留意的是傅立葉變換的精度問題。我們知道，在計算機中實數用單精度數或雙精度數表示，它們會存在一定的誤差。在計算多位數乘法時，n 往往是一個很大的數字，傅立葉變換過程中需要對陣列的每一項進行求和，如何保證精度帶來的誤差不會因為求和而超出允許的範圍？
我的觀點是必須使用雙精度實數，而且由於統計特性，精度帶來的誤差在求和過程中不會很大，一般不會影響計算的正確性。如果需要保證計算的正確性，我想到兩種檢查方法。第一種是取模驗算。
例如，如果乘數和被乘數對 17 的模分別是 8 和 6，那麼積對 17 的模就應該是 14。第二種是檢查運算結果中浮點數偏離整數的最大值。如果偏差只有比如 10-3 量級，我們可以認為這個尺度的乘法運算很安全；如果偏差達到 0.
5，說明運算已經出錯了；如果偏差達到 0.1 量級，那也比較危險，也許換個別的乘數和被乘數就溢位了。
多位數的倒數和開方可以通過牛頓迭代求根法轉化為乘法運算。例如，要計算 x = 1/a ，根據牛頓迭代法令 f(x) = 1/x - a ，可以得到以下迭代序列：
x0 ~= 1/a
xk = xk-1 - f(xk-1)/f'(xk-1) = 2xk-1 - axk-12 (5)
要計算 x = sqrt(a) ，可以先計算 x = 1 / sqrt(a) ，令 f(x) = 1/x2 - a ，可以得到以下迭代序列：
x0 ~= 1 / sqrt(a)
xk = xk-1 - f(xk-1)/f'(xk-1) = (3/2)xk-1 - (1/2)axk-13 (6)
(5) 和 (6) 均以 2 的指數收斂到所求結果。還存在其它更復雜一些的迭代序列，它們以更高的指數收斂，在此不提。不過需要提醒的是，跟 (agm) 不同，這裡 (5) 和 (6) 中的 x0 只是 1/a 和 1 / sqrt(a) 的約值，在前幾次的迭代中不必進行滿 n 位數的乘法運算，因而可以減少計算量。
示例程式
作為 agm 和 fft 算 pi 的完整過程演示，這裡是我新寫的算 pi 程式。很遺憾，我的程式比網上可以找到的其它算 pi 程式慢大約 100 倍，而且消耗更多的記憶體。:-( 目前還不清楚它的瓶頸所在。
不管怎麼說，它總算是我的第一個 agm 和 fft 算 pi 程式，祝賀！:-)
faint-pi-1.0.3.tar.gz c 源程式，在 linux 下以 gcc -std=c99 *.c -o pi -lm -o3 編譯
綜述 以上介紹了三類算 pi 的演算法。第一類演算法的速度最慢，基本上已經過時。後兩類演算法的速度目前相差不大，最為常用。
迭代法雖然在時間複雜度上有理論上的優勢，但實現起來較為複雜，實際上也並不見得比 1/pi 級數法快。
2樓：匿名使用者
周長c/直徑d=3.14159...
圓周率是什麼意思？圓周率是什麼
圓周率是圓的周長與直徑的比值。圓周率 pi 是圓的周長與直徑的比值，一般用希臘字母 表示，是一個在數學及物理學中普遍存在的數學常數。也等於圓形之面積與半徑平方之比，是精確計算圓周長 圓面積 球體積等幾何形狀的關鍵值。在分析學裡，可以嚴格地定義為滿足sinx 0的最小正實數x。圓周率用希臘字母 讀作 ...
圓周率是怎麼匯出的，圓周率是如何計算匯出的
周長除以直徑，因為周長和半徑都很容易測量，最終發現了周長與直徑的關係。圓周率是如何計算匯出的?在中國歷史上，魏晉時，劉徽曾用使正多邊形的邊數逐漸增加去逼近圓周的方法 稱 割圓術 求得 的近似值3.1416。王蕃 229 267 發現了另一個圓周率值，這就是3.156，但沒有人知道他是如何求出來的。公...
請推導圓周率兀的計算公式,謝啦，請推導一個圓周率兀的計算公式,謝啦
第一類演算法 arctan 的級數 pi 4 4 arctan 1 5 arctan 1 239 1 arctan x x x3 3 x5 5 x7 7 2 很容易想到，要得到超高精度的 pi 值，實數在計算機中必須以陣列的形式進行存取，陣列的大小跟所需的有效位數成正比。在這個演算法中，pi 的有效...