算法與圓周率計(jì)算

圓周率一般用π來表示，是一個(gè)在數(shù)學(xué)及物理學(xué)中普遍存在的數(shù)學(xué)常數(shù)。其定義為圓的周長(zhǎng)與直徑之比。常用圓周率的十進(jìn)制近似值為3.141 592 6，另外還有由祖沖之給出的約率：22/7，及密率:355/113。圓周率計(jì)算算法 根據(jù)馬克勞林(Colin Maclaurin)公式有： 在式子兩邊令x=1，得 這個(gè)問題可以使用算法來實(shí)現(xiàn)(見下圖)。 下面介紹歷史上兩個(gè)有名的公式... 更多

圓周率是圓的周長(zhǎng)與直徑的比值，一般用希臘字母π表示，是一個(gè)在數(shù)學(xué)及物理學(xué)中普遍存在的數(shù)學(xué)常數(shù)。π也等于圓形之面積與半徑平方之比。即π=周長(zhǎng)C/直徑d。圓周率公式——幾何算法

憑直觀推測(cè)或?qū)嵨锒攘縼碛?jì)算，實(shí)驗(yàn)階段得到圓周率值的結(jié)果是相當(dāng)粗略的，在眾多數(shù)學(xué)家的努力下，圓周率值的計(jì)算進(jìn)入了科學(xué)的階段——幾何算法階段。

1、圓內(nèi)接、外切多邊形

阿基米德是科學(xué)地研究圓周率這一常數(shù)的第一個(gè)人，開創(chuàng)了幾何計(jì)算圓周率的階段，真正使圓周率計(jì)算建立在科學(xué)的基礎(chǔ)上，他提出了一種能夠借助數(shù)學(xué)過程，把圓周率的值精確到任意精度的方法。

由上圖知，圓周長(zhǎng)大于內(nèi)接正四邊形而小于外切正四邊形，因此2√2 圓周率 4，據(jù)說阿基米德用到了正96邊形才算出這個(gè)值域，這個(gè)例子雖然可行性不強(qiáng)，但它至少邁出了科學(xué)探索圓周率的第一步。

阿基米德求圓周率的更精確近似值的方法，體現(xiàn)在他的一篇論文《圓的測(cè)定》之中。在這一書中，阿基米德第一次使用上、下界來確定圓周率的近似值，他用幾何方法證明了“圓周長(zhǎng)與圓直徑之比小于3+1/7而大于3+10/71”，而且提供了誤差的估計(jì)方法及計(jì)算。重要的是，這種方法從理論上而言，能夠求得圓周率的更準(zhǔn)確的值。

到公元150年左右，希臘天文學(xué)家托勒密得出圓周率=3.1416，這是自阿基米德以來取得的巨大進(jìn)步。

2、割圓術(shù)的應(yīng)用

割圓術(shù)(下圖)是我國(guó)的數(shù)學(xué)家劉徽提出的，他是我國(guó)最早運(yùn)用科學(xué)方法計(jì)算圓周率值的人，在公元263年前后，他就用此方法得出π=3.14，后人稱之為“徽率”，他指出這是不足近似值。雖然他提出割圓術(shù)的時(shí)間比阿基米德晚一些，但其方法確有著更美妙之處。

割圓術(shù)僅用內(nèi)接正多邊形就確定出了圓周率的上、下界，比阿基米德同時(shí)用內(nèi)接和外切正多邊形的方法簡(jiǎn)捷得多。另外，有人認(rèn)為在割圓術(shù)中劉徽提供了一種絕妙的精加工方法，以致于他將割到192邊形的幾個(gè)粗糙的近似值通過簡(jiǎn)單的加權(quán)平均，竟然獲得具有4位有效數(shù)字的圓周率π=3927/1250=3.1416。而這一結(jié)果，正如劉徽本人指出的，如果通過割圓計(jì)算得出這個(gè)結(jié)果，需要割到3072邊形，這種精加工方法的效果是奇妙的，也是割圓術(shù)中最為精彩的部分。

令人遺憾的是，由于人們對(duì)它缺乏理解而被長(zhǎng)期遺忘了。大家更加熟悉的是祖沖之的兩大貢獻(xiàn)：其一是求得圓周率3.1415926 π 3.1415927，其二是，得到圓周率的兩個(gè)近似分?jǐn)?shù)，即約率為22/7，密率為355/133。他算出的圓周率的8位可靠數(shù)字，不但在當(dāng)時(shí)是最精密的圓周率，而且保持世界記錄九百多年，以致于有數(shù)學(xué)史家提議將這一結(jié)果命名為“祖率”。

在這一時(shí)期，數(shù)學(xué)家們對(duì)圓周率精確值的探索頗有成就，涌現(xiàn)出了大量的偉人，阿基米德、祖沖之、魯?shù)婪虻?，他們都為圓周率的計(jì)算做出了卓越的貢獻(xiàn)。但是，用幾何方法求其值，計(jì)算量很大，這樣算下去，窮數(shù)學(xué)家的一生也改進(jìn)不了多少。

古典方法已引導(dǎo)數(shù)學(xué)家們走了很遠(yuǎn)，到魯?shù)婪蚩梢哉f已經(jīng)登峰造極，再向前推進(jìn)，必須在方法上有所突破。圓周率公式——分析算法

17世紀(jì)出現(xiàn)了數(shù)學(xué)分析這一銳利的工具，使得許多初等數(shù)學(xué)束手無策的問題迎刃而解，圓周率的計(jì)算歷史也隨之進(jìn)入一個(gè)新的階段。

1、圓周率公式與解析表達(dá)式

1579年法國(guó)數(shù)學(xué)家韋達(dá)在(《數(shù)學(xué)定律，應(yīng)用于三角形》中)通過計(jì)算圓的正6×216=393216邊形，得出3.1415926535 π 3.1415926537，同時(shí)他利用分析式和級(jí)數(shù)乘積來刻畫圓周率。

這個(gè)式子給科學(xué)家們指出了一個(gè)嶄新的計(jì)算圓周率的思路，這是分析法計(jì)算圓周率時(shí)代的第一個(gè)解析表達(dá)式。這個(gè)公式的優(yōu)美至今令我們贊嘆不已，它僅僅借助數(shù)2，通過一系列的加、乘、除和開平方就可算出圓周率值，且將圓周率計(jì)算到了第九位。

這一時(shí)期，是幾何算法與分析算法“共同繁榮”的時(shí)期，在1621年德國(guó)-荷蘭物理學(xué)家、數(shù)學(xué)家斯涅耳對(duì)原來古典方法作出了一些三角上的改進(jìn)，利用這一改進(jìn)，只需算到230邊形，就可得到34位圓周率值。1630年，意大利羅馬數(shù)學(xué)家格林貝格(利用斯涅耳的方法得到40位。這也是利用多邊形周長(zhǎng)算圓周率的最后的重要結(jié)果。

2、圓周率公式與反正切函數(shù)表達(dá)式

1669年，牛頓在在他的《分析學(xué)》中提出后，蘇格蘭數(shù)學(xué)家詹姆斯·格雷戈里公開了牛頓的arctanx的級(jí)數(shù)展開式。

只可惜，沒有發(fā)現(xiàn)只需令式x=1中，就可以得到π/4=1-1/3+1/5-1/7+…，致使他就此裹足不前。這個(gè)公式后來由萊布尼茲發(fā)現(xiàn)，這個(gè)級(jí)數(shù)被稱為萊布尼茲級(jí)數(shù)。從此，數(shù)學(xué)家們以反正切函數(shù)計(jì)算值擺開了強(qiáng)大的陣容。在1706年英國(guó)數(shù)學(xué)家、天文學(xué)家梅欽發(fā)現(xiàn)了Machin公式

利用此公式將圓周率的值計(jì)算到了100位。1734至1735年，在前人的基礎(chǔ)上，歐拉經(jīng)過不懈地努力和探索終于得出著名的歐拉公式

到了1737年，歐拉利用反正切函數(shù)arctan1=π/4，根據(jù)格雷戈里的展開式將右邊展開，得到了著名的歐拉級(jí)數(shù)，

1841年，英國(guó)威廉·盧瑟福利用格雷戈里的級(jí)數(shù)和公式計(jì)算到π的208位，后來發(fā)現(xiàn)其中的152位是正確的。1844年，僅花了兩個(gè)月時(shí)間，德國(guó)漢堡的數(shù)學(xué)家斯特拉斯尼茨基和達(dá)什使用施瓦茲公式計(jì)算到小數(shù)點(diǎn)后205位，但只有200位正確。1877年，歷史上另一位類似于魯?shù)婪虻挠?guó)數(shù)學(xué)家尚克斯利用梅欽公式并借助臺(tái)式機(jī)械計(jì)算機(jī)花了30年時(shí)間將圓周率計(jì)算到707位。

但在1945年，福格森出于篤信圓周率是簡(jiǎn)單正態(tài)數(shù)，用手工計(jì)算機(jī)對(duì)尚克斯的的結(jié)果進(jìn)行了核實(shí)，發(fā)現(xiàn)從528位起是錯(cuò)的?！翱蓱z的尚克斯”，不僅幾十年的心血大多打了“水漂”，最主要的是，他至死都不知道，他已經(jīng)出錯(cuò)了。在尚克斯的結(jié)果發(fā)表之后不久，中國(guó)著名的數(shù)學(xué)家李善蘭在用尖錐術(shù)求圓面積的時(shí)候得到了式子

這個(gè)式子的發(fā)現(xiàn)，足以證明我國(guó)在繼祖沖之之后對(duì)圓周率的探索仍然大有作為。1848年1月，福格森和雷恩奇聯(lián)合發(fā)表了經(jīng)過檢驗(yàn)的正確的圓周率的808位。1949年，英國(guó)數(shù)學(xué)家列維·史密斯和雷恩奇算出圓周率的1121位，是人工算圓周率的最高記錄。

這一時(shí)期，人們對(duì)圓周率的計(jì)算可以說是有相當(dāng)大的進(jìn)展，學(xué)會(huì)使用解析表達(dá)式來計(jì)算圓周率的值，而且，有了計(jì)算方法的最大突破——圓周率的反正切函數(shù)表達(dá)式的發(fā)現(xiàn)，這個(gè)公式層出不窮，為計(jì)算圓周率的更精確的值提供了有力的科學(xué)依據(jù)。

隨著人們對(duì)圓周率探索的發(fā)展，計(jì)算工具也在不斷的改進(jìn)，最開始自制的不精確的工具逐漸被淘汰，手盤和算盤成了大多人計(jì)算的工具，計(jì)算量不斷增大，這兩種計(jì)算工具已經(jīng)不能滿足數(shù)學(xué)家們的計(jì)算要求。此時(shí)，臺(tái)式機(jī)械計(jì)算機(jī)出現(xiàn)了，它為數(shù)學(xué)家們的計(jì)算提供了方便。但人們并沒有停止對(duì)計(jì)算工具的研究和更新，腳步依然在前進(jìn)。

3、圓周率公式與概率方法

關(guān)于圓周率的值，歷史上還有一種幾何與分析思想之外的方法，那就是18世紀(jì)法國(guó)科學(xué)家蒲豐創(chuàng)造的“投針求的概率論方法”。

問題：將長(zhǎng)為l的勻質(zhì)細(xì)針隨機(jī)地?cái)S于畫了等距平行線族的平面上，相鄰兩平行線距離為a，a l，求針與平行線相交的概率。

具體解法：設(shè)x為針中點(diǎn)到平行線的距離，則x∈[0，a/2]，設(shè)θ為針與平行線的夾角，則θ∈[0，π]。

由上圖知，當(dāng)且僅當(dāng)0≤x≤1/2·sinθ，θ∈[0，π]時(shí)針與平行線相交，于是所求概率：

p=陰影面積矩形OABC面積-2l/π，于是π=2l/ap。

1901年，意大利數(shù)學(xué)家拉澤里尼投針3408次，他用壓線的頻率代替概率p，即取p=m/3408，求得π=3.141592。當(dāng)投針次數(shù)愈多，求得π值將愈精確。在用概率方法計(jì)算圓周率值中，值得我們特別關(guān)注的是1904年，R·查特發(fā)現(xiàn)的“兩個(gè)隨意寫出的數(shù)互素的概率為6/π2”。英國(guó)伯明翰市阿斯頓大學(xué)計(jì)算機(jī)科學(xué)與應(yīng)用數(shù)學(xué)系的羅伯特·馬修斯，利用夜空中亮星的分布來計(jì)算圓周率，他從100顆最亮的星星中隨意選取一對(duì)又一對(duì)進(jìn)行分析，計(jì)算它們位置之間的角距且檢查了100萬對(duì)因子，據(jù)此求得π的值約為3.12772，這個(gè)值與真值相對(duì)誤差不超過5%。

概率方法的出現(xiàn)，使圓周率的計(jì)算又一次靠近了精確值，而數(shù)學(xué)家們并沒有為此沾沾自喜，探索還在繼續(xù)……圓周率公式與電子計(jì)算機(jī)

眾所周知，電子計(jì)算機(jī)的產(chǎn)生及應(yīng)用給人們的生活和工作帶來了很大的方便，同時(shí)，它不僅為數(shù)學(xué)家們計(jì)算圓周率值帶來前所未有的突破，也使圓周率的計(jì)算進(jìn)入了一個(gè)新的時(shí)代。1949年，人類第一次在美國(guó)馬里蘭州阿伯丁的軍隊(duì)彈道研究實(shí)驗(yàn)室里用電子計(jì)算機(jī)算圓周率，包括馮·諾伊曼在內(nèi)，用ENIAC和梅欽公式計(jì)算圓周率值到2048位，突破了千位數(shù)。1959年，美國(guó)國(guó)際商業(yè)機(jī)器公司(IBM)制成第二代電子計(jì)算機(jī)——世界上的一臺(tái)晶體管電子計(jì)算IBM-7090。

1961年，丹尼爾·尚克斯和華盛頓的雷恩奇用IBM-7090分別使用挪威斯托默公式：

和高斯公式：

將圓周率計(jì)算到小數(shù)點(diǎn)后100256位，終于登上110萬位高峰。1985年，喬納森·波爾文和彼得·波爾文發(fā)表波爾文算法：

初值：a0=6-4√2，y0=√2-1，

重復(fù)計(jì)算：

和

最后得到π=1/an，它四次收斂于圓周率π。

屢創(chuàng)紀(jì)錄的出生在蘇聯(lián)的美國(guó)哥倫比亞大學(xué)的戴維德·丘德諾夫斯基和格雷戈里·丘德諾夫斯基兄弟，丘德諾夫斯基兄弟將LM公式改良為式子

這個(gè)公式稱為丘德諾夫斯基公式，簡(jiǎn)記“QD”，每計(jì)算一項(xiàng)可以得到圓周率的15位十進(jìn)制精度，他的另一個(gè)更方便于計(jì)算機(jī)編程的形式是，

丘德諾夫斯基兄弟利用此公式，在96年的時(shí)候得到80億位圓周率的值。

計(jì)算機(jī)的產(chǎn)生，使圓周率的計(jì)算達(dá)到了驚人的程度，圓周率的值達(dá)到難以想象的精度，再繼續(xù)研究計(jì)算圓周率的精度已經(jīng)變得意義不大。