算法與圓周率計(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)變得意義不大。