周長除以直徑
古人計算圓周率,一般是用割圓法.即用圓的內接或外切正多邊形來逼近圓的周長.Archimedes用正96邊形得到圓周率小數點後3位的精度；劉徽用正3072邊形得到5位精度；Ludolph Van Ceulen用正262邊形得到了35位精度.這種基於幾何的演算法計算量大,速度慢,吃力不討好.隨著數學的發展,數學家們在進行數學研究時有意無意地發現了許多計算圓周率的公式.下面挑選一些經典的常用公式加以介紹.除了這些經典公式外,還有很多其它公式和由這些經典公式衍生出來的公式,就不一一列舉了.
1、 Machin公式
[這個公式由英國天文學教授John Machin於1706年發現.他利用這個公式計算到了100位的圓周率.Machin公式每計算一項可以得到1.4位的十進位制精度.因為它的計算過程中被乘數和被除數都不大於長整數,所以可以很容易地在計算機上程式設計實現.
Machin.c 源程式
還有很多類似於Machin公式的反正切公式.在所有這些公式中,Machin公式似乎是最快的了.雖然如此,如果要計算更多的位數,比如幾千萬位,Machin公式就力不從心了.下面介紹的演算法,在PC機上計算大約一天時間,就可以得到圓周率的過億位的精度.這些演算法用程式實現起來比較複雜.因為計算過程中涉及兩個大數的乘除運算,要用FFT(Fast Fourier Transform)演算法.FFT可以將兩個大數的乘除運算時間由O(n2)縮短為O(nlog(n)).
2、 Ramanujan公式
1914年,印度數學家Srinivasa Ramanujan在他的論文裡發表了一系列共14條圓周率的計算公式,這是其中之一.這個公式每計算一項可以得到8位的十進位制精度.1985年Gosper用這個公式計算到了圓周率的17,500,000位.
1989年,David & Gregory Chudnovsky兄弟將Ramanujan公式改良成為：
這個公式被稱為Chudnovsky公式,每計算一項可以得到15位的十進位制精度.1994年Chudnovsky兄弟利用這個公式計算到了4,044,000,000位.Chudnovsky公式的另一個更方便於計算機程式設計的形式是：
3、AGM(Arithmetic-Geometric Mean)演算法
Gauss-Legendre公式：
這個公式每迭代一次將得到雙倍的十進位制精度,比如要計算100萬位,迭代20次就夠了.1999年9月Takahashi和Kanada用這個演算法計算到了圓周率的206,158,430,000位,創出新的世界紀錄.
4、Borwein四次迭代式：
這個公式由Jonathan Borwein和Peter Borwein於1985年發表,它四次收斂於圓周率.
這個公式簡稱BBP公式,由David Bailey,Peter Borwein和Simon Plouffe於1995年共同發表.它打破了傳統的圓周率的演算法,可以計算圓周率的任意第n位,而不用計算前面的n-1位.這為圓周率的分散式計算提供了可行性.1997年,Fabrice Bellard找到了一個比BBP快40％的公式：
周長除以直徑
古人計算圓周率,一般是用割圓法.即用圓的內接或外切正多邊形來逼近圓的周長.Archimedes用正96邊形得到圓周率小數點後3位的精度；劉徽用正3072邊形得到5位精度；Ludolph Van Ceulen用正262邊形得到了35位精度.這種基於幾何的演算法計算量大,速度慢,吃力不討好.隨著數學的發展,數學家們在進行數學研究時有意無意地發現了許多計算圓周率的公式.下面挑選一些經典的常用公式加以介紹.除了這些經典公式外,還有很多其它公式和由這些經典公式衍生出來的公式,就不一一列舉了.
1、 Machin公式
[這個公式由英國天文學教授John Machin於1706年發現.他利用這個公式計算到了100位的圓周率.Machin公式每計算一項可以得到1.4位的十進位制精度.因為它的計算過程中被乘數和被除數都不大於長整數,所以可以很容易地在計算機上程式設計實現.
Machin.c 源程式
還有很多類似於Machin公式的反正切公式.在所有這些公式中,Machin公式似乎是最快的了.雖然如此,如果要計算更多的位數,比如幾千萬位,Machin公式就力不從心了.下面介紹的演算法,在PC機上計算大約一天時間,就可以得到圓周率的過億位的精度.這些演算法用程式實現起來比較複雜.因為計算過程中涉及兩個大數的乘除運算,要用FFT(Fast Fourier Transform)演算法.FFT可以將兩個大數的乘除運算時間由O(n2)縮短為O(nlog(n)).
2、 Ramanujan公式
1914年,印度數學家Srinivasa Ramanujan在他的論文裡發表了一系列共14條圓周率的計算公式,這是其中之一.這個公式每計算一項可以得到8位的十進位制精度.1985年Gosper用這個公式計算到了圓周率的17,500,000位.
1989年,David & Gregory Chudnovsky兄弟將Ramanujan公式改良成為：
這個公式被稱為Chudnovsky公式,每計算一項可以得到15位的十進位制精度.1994年Chudnovsky兄弟利用這個公式計算到了4,044,000,000位.Chudnovsky公式的另一個更方便於計算機程式設計的形式是：
3、AGM(Arithmetic-Geometric Mean)演算法
Gauss-Legendre公式：
這個公式每迭代一次將得到雙倍的十進位制精度,比如要計算100萬位,迭代20次就夠了.1999年9月Takahashi和Kanada用這個演算法計算到了圓周率的206,158,430,000位,創出新的世界紀錄.
4、Borwein四次迭代式：
這個公式由Jonathan Borwein和Peter Borwein於1985年發表,它四次收斂於圓周率.
這個公式簡稱BBP公式,由David Bailey,Peter Borwein和Simon Plouffe於1995年共同發表.它打破了傳統的圓周率的演算法,可以計算圓周率的任意第n位,而不用計算前面的n-1位.這為圓周率的分散式計算提供了可行性.1997年,Fabrice Bellard找到了一個比BBP快40％的公式：