為什麼我們總是在計算圓周率π?因為沒有最快,只有更快!

2020-12-13 徐曉亞然

自從人們學會了用越來越多的方法來求圓周率,似乎在怎麼求圓周率的研究上已經信心十足。你提出100種要求來得到圓周率的值,那我就能想到101種方法來求解圓周率。的確,人們在這項事業上可以說是蒸蒸日上,從上古時代的割圓術,到萊布尼茲級數,投針實驗,以及各種各樣的無窮級數等等。每一種方法到最後都可以把圓周率精準無誤地的出來,然而這並不意味著,這每一種方法實施起來都是一樣的效果。這裡就必須考慮一個執行效率的問題。

永無休止的π

這裡不考慮遙遠時代的割圓術了,在兩千年前的古人能得出這樣的算法就已經很不容易了,你還要求他們,割圓術求π太慢了,能不能找個更快的。這樣就太過苛刻了,這樣苛刻的要求應該要放在微積分時代的人們身上才顯得公平。

萊布尼茨

萊布尼茨級數

我們再來回顧一下萊布尼茨大神的得意之作,這個式子很容易記,可操作性也不錯。但是若需要在很短時間內去求很多位數的圓周率值,這個級數其實是不實用的。為什麼呢?因為這個級數的收斂速度太慢了!人們用計算機模擬過,大約要計算500000項,才能精確到小數點後5位。這樣的執行效率實際中會有人採用嗎,反正我是不會,因為我將浪費大量的時間和資源在那裡兜兜轉轉才勉強達到的精度值上。

歐拉大神

巴塞爾級數

那再來看看歐拉大神的揚名之作,巴塞爾級數,這個級數的和也是一個包含π的數字。這個級數求和過程十分精彩,但是如果你也想通過這個公式來求圓周率那就大錯特錯了。雖然理論上,巴塞爾級數的收斂速度不會像萊布尼茲級數一樣出奇地慢,但是也基本上也要計算到10000項,才能精確到小數點3位。所以,如果我來選擇一種算法求解圓周率,這兩大鼎鼎有名的公式第一輪就會被pass掉。

於是,我們想在圓周率問題上有所突破,就必須去找一些快,準,狠的算法,不對,應該是快,易,準的方法。

梅欽公式

1706年,英國數學家梅欽提出了一個收斂速度不錯的公式,令人驚訝的是這個公式完全沒有用到微積分,也沒有採用無窮級數,僅僅是三角函數變換就得到了。這個公式是這樣子的。

梅欽公式

是不是覺得這個公式有點莫名其妙,好像兩邊驢唇不對馬嘴之間也可以建立如此漂亮的等式關係。雖然看起來怪異,但是這個公式還是很好證明出來的。

梅欽公式推導

得到這個反正切的公式之後,我們利用梅欽公式計算圓周率就已經完成了一大半了。那接下來呢,我們就要用親愛的泰勒級數展開式把反正切轉換成具體可以計算的形式,其中反正切的泰勒級數展開形式是這樣子。

反正切函數泰勒展開式

特別的,如果我們對於精度很執著,那麼需要計算的式子項數就會格外地多在項數過多的情況下,這樣的計算量仍然是可以簡化的。這裡就不得不提到我國古代一位數學家的成就,這就是秦九韶算法,在高次多項式數值計算時,可以極大地減少計算複雜度,也特別容易通過程序來實現。

數學家 泰勒

秦九韶算法和梅欽公式相結合,使得這套計算算法成為歷史上第一個快速求圓周率算法。1706年,英國數學家梅欽本人利用這個公式將圓周率計算到了小數點後100位,這在割圓術時代是根本無法想像的,至於為什麼是這樣子的,請參考魯道夫窮盡一生用割圓術才計算到小數點35位而已。

我國古代著名數學家 秦九韶

後來出現了許多類梅欽公式,都是利用反正切函數的組合。人們用差不多的風格去改造梅欽公式,在這方面做到巔峰的應該是這位,英國的謝克斯。他利用這類公式把圓周率計算到了小數點後707位,這個也是人工計算圓周率取得的最高紀錄。不過可惜的是,後人檢查他的計算結果,發現第528位是錯誤的,所以在528位之後的結果就都是錯誤的了。

秦九韶算法原理 轉自維基百科

拉馬努金公式

雖然說梅欽公式的極大得改進了求π的進程,但是如果我們想計算千萬位圓周率數字,梅欽公式就顯得力不從心了。然而數學家們的追求是無止境的,琢磨琢磨就總會有新的玩意出來,一句話,求π公式裡沒有最快只有更快。這裡就需要一位超級大神再一次搬出來了,印度的傳奇數學家,拉馬努金。

拉馬努金

拉馬努金,1887年出生在印度的小鎮上,從小家庭貧困,生活艱難,不過好在他很早就發現自己在數學上有著常人無可比擬的天賦。在那個印度教育普遍不行的情況下, 拉馬努金靠著一本記載了5000個公式的數學教普書《純粹數學與應用數學概要》。他完全自學,掌握了最高級的數學技巧,他甚至補全了那本書中很多缺少的內容,比如很多高級公式的證明。這本書也決定了拉馬努金日後的研究方向,他受到這本書的啟發,日後提出了許許多多駭人聽聞的公式,大約有3900個,絕大多數都是對的。任何一個數學愛好者都會把這些公式當成是寶藏一般,細心研究的。

比如,他曾經提出過很多關於求π的公式,這些公式都有以下幾個特點:等號右邊的構造超乎常人想像,收斂速度極快!比如這個拉馬努金在1914年發布的以他自己名字命名著名公式。

拉馬努金公式

我們普通人根本難以想像等式後邊的部分如此繁雜無序,確實深深地與π產生等價關係,事實上,人們也是在研究了很久才得知拉馬努金是如何得出這樣的公式的。這是來自高深的橢圓積分函數,我們不去深刻研究如何由橢圓積分函數推導出上面這個式子,這已經超過曉然菌的能力了。我們只是來欣賞一下這樣的式子究竟有多厲害就行了。

拉馬努金筆記

右邊的組成部分雖然紛繁複雜,但是倘若我們一項一項地來整理還是比較容易用編程的方法來實現的。現在利用一臺簡單的的計算器來進行,我們發現只要計算一次,精度就會超過計算器能夠顯示的有效位數。大概這裡的k每次累加計算一次,我們就會得到圓周率8位有效數字。也就是說,你只要進行第一步計算,其結果就大大超過了萊布尼茨公式50萬步計算的總和,這是一個何其壯哉的進步!當然,當年拉馬努金髮現這個公式的初衷可不是為了圓周率計算,可能他也完全沒有想過這個公式有著如此恐怖的計算速度。

Chudnovsky公式

在進入到了計算機時代,有些算法如果易於編程,便立刻會有極其龐大的計算成果出現。1985年,Gosper利用拉馬努金公式,用計算機得到圓周率小數點後1750萬位。然而,有人仍然覺得拉馬努金公式有深度可挖,這個公式應該也會像梅欽公式一樣,可以繼續改進,獲得更加恐怖的收斂速度。

David Chudnovsky

1989年,Chudnovsky兩兄弟在一起合作,將拉馬努金公式改進不少,這個公式也當之無愧地稱為Chudnovsky公式。比起拉馬努金公式,這兩兄弟得到的公式就更加鬼畜了。就是下面這個。

Chudnovsky公式

這個公式可不得了,之前拉馬努金公式每計算一項可以獲得8位有效數字已經很了不起了,然而他們的這個公式居然可以做到每計算一項得出15位有效數字!1994年,他們利用這個強大的公式,得到了圓周率小數點後40.44億位。

你以為到了這裡就結束了麼?當然沒有,人們對於算法的改進是永無止境的,很多算法在手工時代看不出效率高低,但是一旦拿到計算機上執行,在計算到百萬位,上億位之後,是一定能分得清效率高低的。

高斯勒讓德迭代公式

現在我們的計算機還是只能根據指令來計算的,可能在以後會有別的方式來主導它的計算。它不怕繁雜重複的執行命令,只要你給時間和存儲空間,如果算法得當,那麼就一定會有一個結果出來。比如,計算機最喜歡做的就是迭代計算,所謂迭代,就是把一個大問題先分解成很多個小過程,小過程的計算很簡單,但是後面一步的計算是建立在前一步的基礎上的。如果問題足夠麻煩,可能會有非常多的小步驟,如果你只盯著其中的一小步,你會覺得這樣的計算毫無意義,很難讓你有著繼續下去的動力。

勒讓德

比如斐波那契數列的定義,這就是一個最簡單的迭代方式:後一項總是前面兩項的和。倘若我們不知道這個數列的通項公式,那就只能用這樣近乎呆滯的方法一步一步來算。比如讓你求斐波那契數列的第30項,這個計算量對於人工來說就已經很龐大了。然而,這樣迭代的計算過程對於機器來說,卻是最擅長的事情了。

斐波那契數列遞推關係

有一個著名的圓周率迭代計算方法,這個迭代算法的收斂速度已經到了一種登峰造極的地步。高斯勒讓德迭代算法。

高斯勒讓德算法 轉自維基百科

這個算法並不是高斯和勒讓德得出的,而是1975年理察·布倫特和尤金·薩拉明基於上面兩位大神的某些成果獨立發現的。和別的迭代公式類似,初始值很簡單,每一步計算難度也不大。不過這個收斂的速度,怎麼形容呢?這套算法只要迭代25次就可以得到4500萬位有效數字!1999年,日本的高橋大介和金田康正用這個算法計算到了圓周率的2061億位數字,創造了當時的世界紀錄。

多次打破圓周率世界紀錄的金田康正

2019年3月14日,一位日裔女程式設計師艾瑪利用谷歌雲平臺計算引擎得到了圓周率31.4萬億位數字,這也是人類目前的新紀錄。這樣的成果是在谷歌雲平臺計算引擎上使用了25臺虛擬機,歷時4個多月得到的,整個計算過程中一共產生了大約170TB的數據,他們使用的就是Chudnovsky公式。

日裔女程式設計師艾瑪

31.4萬億位當然不是人類追求圓周率數值計算的終點,每一次數值裡程碑背後都附帶著一個當時最先進的算法。到目前為止,人們仍然孜孜不倦地探索著求圓周率的新算法,我們的最終目的不是求到了多少多少位圓周率,而是在計算圓周率的過程中,我們可以檢驗很多內容深刻的算法。用更少的時間,更小的空間,更少的資源來獲得更多精準的數據。

超級計算機 晝夜不停計算圓周率

從人工計算到機器計算,關於圓周率的各路求法其實也代表了科學水平的發展水平。尤其是現代計算機算力的加成讓算法越來越深刻,成果也越來越豐富。我們也會在這條計算的道路上一直走下去,永不停息!

相關焦點

  • 圓周率π的計算曆程
    因而當我們稱頌祖衝之的功績時,不要忘記他的成就的取得是因為他站在數學偉人劉徽的肩膀上的緣故。後人曾推算若要單純地通過計算圓內接多邊形邊長的話,得到這一結果,需要算到圓內接正12288邊形,才能得到這樣精確度的值。祖衝之是否還使用了其它的巧妙辦法來簡化計算呢?這已經不得而知,因為記載其研究成果的著作《綴術》早已失傳了。這在中國數學發展史上是一件極令人痛惜的事。
  • 圓周率π的計算曆程及各種腦洞大開的估計方法
    作為一個非常重要的常數,圓周率最早是出於解決有關圓的計算問題。僅憑這一點,求出它的儘量準確的近似值,就是一個極其迫切的問題了。回顧歷史,人類對 π 的認識過程,反映了數學和計算技術發展情形的一個側面。 π 的研究,在一定程度上反映這個地區或時代的數學水平。為求得圓周率的值,人類走過了漫長而曲折的道路,它的歷史是饒有趣味的。我們可以將這一計算曆程分為幾個階段。
  • 圓周率π是如何計算得到的
    圓周率是很多人在小學階段就接觸的一個數,關於它的知識可以從小學一直貫穿到無窮盡。
  • 追尋蘊藏在圓周率 π 之中的無限美麗
    這就像試圖到達月球,然後目標就是到達下一個火星,以此類推……但為什麼?為什麼數學家要費心計算更多的位數呢?為什麼 34.1 萬億位的 π 還不夠?是因為圓周率蘊藏在每一個圓之中嗎?另一方面,我們人類總是去嘗試攀登更高的山,潛入更幽深海溝……或者嘗試著去記住 π 小數點後面的數字,比如呂超,他準確無誤地背住了 π 小數點後的前 67,890 位。人們一直都在挑戰做著這些嘗試是因為想要更了解所生活的這個世界。
  • 從小學到大學都能看懂的圓周率π的計算方式
    如下是著名的萊布尼茲公式,你可以從許多途徑來推導,但你有沒有嘗試過用幾何方法來證明呢?在1932年的一本數學著作《幾何與想像力》中詳細地討論了這種方法,它的作者就是大名鼎鼎的數學全才希爾伯特。這本書展現了非凡的幾何思維,在國外很受歡迎。
  • 圓周率π數字背後隱藏的秘密,遠沒有你想的那麼簡單!
    早在公元前二十世紀,就有人類發現了一個神奇的數字,那就是π,那時候的人類只能將π的數值精確計算到好後一位。之後人類並沒有放棄圓周率的計算,並且開始嘗試用各種各樣的辦法,終於在公元480年,我國的祖衝之將圓周率計算到了後面七位。
  • 圓周率π已被計算到了31.4萬億位,繼續計算下去有何意義?
    圓周率π作為一個無理數(無線不循環小數),在日常實際生活中,通常只用到近似值3.14進行計算,只有科學家們為了精確計算才會用到十位小數,甚至幾百位小數進行精確精算。在中國的古代,人們從實踐中就知道圓的周長是「圓徑一而周三有餘」,意思是說圓直徑的三倍多等於圓的周長,三倍多要多多少,成了一個非常難的研究課題。
  • 用Scratch來計算圓周率π,小朋友也能懂
    之前電腦報刊登了一篇用VB計算圓周率π值的文章。使用了π/4=1-1/3+1/5+…+1/i,計算π的近似值,i值越大精度越高。這種算法不夠直觀,其實不太容易理解。我另外選了兩種計算π的算法:蒙特卡羅方法和直接測量法,並用Scratch編程來計算圓周率,這樣小朋友都能很容易理解圓周率的定義和計算了。
  • 圓周率π,不得不說的一個數
    圓周率與圓周率的計算+圓周率簡介圓周率π(Ratio of circumference to diameter;Pi)是圓的周長與直徑的比值,一般用希臘字母π表示,是一個在數學及物理學中普遍存在的數學常數。π也等於圓形之面積與半徑平方之比。
  • 圓周率π的故事
    在遠古時期,人們就知道圓周長P與直徑D的比值是不變的,即不論圓多大,比值P/D不變(叫圓周率).英國語言學家威廉·瓊斯(William Jones,1746—1794)於1706年第一個採用π表示圓周率.π在很多數學公式中出現,如圓周長、圓面積、球體積、橢圓面積A=πab等.π究竟是多少?
  • 愛折騰的無理數-圓周率π
    本文參加百家號科學#了不起的基礎科學#系列徵文從前有個教書先生喜歡喝酒,每次總是人給學生留道題,就到私塾的後山上找老和尚喝有酒。一天,他讓學生背圓周率,自己就跑去喝酒了。你知道圓周率是怎麼來的嗎?圓周率,一般以來表示,是一個在數學及物理學經常出現的數學常數。它的定義就是圓形周長與直徑的比,也等於圓形之面積與半徑平方的比,它是精確計算圓周長、圓面積、球體積等幾何形狀的關鍵值是一個無理數,也就是一個無限不循環小數。
  • 物理學家在量子力學中發現圓周率π的計算公式
    圓周率π圓周率π是圓的周長和其直徑的比值,這是一個常數,在數學中是非常重要的。經過數千年的努力,人類已經能夠計算出相當精確的圓周率數值。它的計算公式有很多種,可以用無窮級數來表示,比如數學家萊布尼茨發現的計算圓周率公式:
  • 學了這麼多年數學,什麼是π?不是圓周率!
    π是希臘字母,用於表示最廣為人知的數學常數——圓周率根據定義,圓周率是圓周長與其直徑之比換句話說,π=周長除以直徑(π= c / d)這個數字大約等於,我們知道π的值是3.14或3.14159雖然這都是近似數,總會有誤差於是有些人用有理表達式來表示π,比如22/7 (333/106)π的計算
  • 圓周率的涵義你知多少(二):π與量子力學
    圓周率的涵義你知多少?的文章裡,我們就關於圓周率π的涵義的一些最基本而又重要的問題,儘量用最通俗的語言予以了最簡單的解釋。由於篇幅所限,這裡不便解釋公式及其符號具體含義,目的只在於是了解公式中圓周率π的呈現。普朗克常數基於上述普朗克在研究物體熱輻射的規律的發現,只有假定電磁波的發射和吸收不是連續的,而是一丁點一丁點地進行的,計算的結果才能和實驗結果相符。
  • 傳奇數學家用圓周率π破案 π究竟牛B在哪裡?
    圓周率π是一個非常神奇的數字,它定義為圓形之周長與直徑之比,也是圓形之面積與半徑平方之比。它可能是世界上最具傳奇色彩的無限不循環小數,不僅是眾多數學物理公式的關鍵要素,也曾幫助數學家破獲驚天殺人案,π到底有多牛B?
  • 圓周率都算到十萬億位了,為什麼還要計算?到底有什麼用?
    我相信你對圓周率很熟悉,因為它是一個無限的不循環數,所以當我們使用它時,我們只能用「π」來代替,或者近似於3.14。但是,我們不要看已經認定了這個事實,但是關於圓周率仍然有許多挑戰。不要說孩子們能背誦多少個數字。即使是超級計算機也在日夜計算。這有什麼用?
  • 成功將圓周率π計算到小數點後31.4萬億位數
    國際圓周率日這天,谷歌工程師成功將圓周率π計算到小數點後31.4萬億位數字,比上一次記錄多了9萬億位! 昨天是 3 月 14 日,也是國際圓周率日。 在這天,一位谷歌工程師創造了一項世界紀錄!12 歲時,她就試過自己下載軟體,試圖計算圓周率 π。 Iwao 在谷歌雲官方博客上詳細介紹了這次的計算過程,並且,所計算出來的 31.4 萬億個數字也已經成為開放資源可供下載,歡迎所有想用這些數字做實驗的人下載使用。 121天,使用雲計算的優勢 自古巴比倫人以來,人們就沒有停止過計算圓周率 π。π 是一個無限不循環小數,為一個圓的周長和其直徑的比率。
  • 3月14日:圓周率日淺說 π
    有些人也許在下午1時59分慶祝,以象徵圓周率π的六位近似值3.14159,有的甚至精確到26秒,以象徵圓周率的八位近似值3.1415926;有的以24小時計時在凌晨1時59分或者下午3時9分(15時9分)慶祝。值此今年不同尋常的圓周率π日之際,選個時刻,好好地祝福自己、祝福親友:一「派」安康、一「派」吉祥。這裡用圖文最簡單、最通俗地說一說 π 的基本常識 。
  • 為什麼說使用圓周率π可能是一個巨大的錯誤?
    今天是3月14日,這是一年一度的圓周率日,世界各地的數學愛好者都會慶祝這一特別的節日。但也有數學家對此潑冷水,他認為用3.141592653…作為圓周率(π)或許是個巨大的錯誤。這可能會讓那些記住了7萬位圓周率小數位的人(目前只有兩人能夠做到)感到詫異,他們或許會最早站出來反對這樣的事情。當然,這並不是說圓周率的具體數值算錯了,也不是說圓周率不是無理數和超越數。根據猶他谷大學數學系系主任Bob Palais教授,應該用2π(記作τ)來作為圓周率更合適。
  • 「π」會不會被算盡?數學家:圓周率算盡就完蛋了!
    我們普通人知道的π當然與數學家研究的π不一樣,在數學家眼裡,π不是3.14,而是3.141592653……對於數學家來說,π是一個挑戰、一個難關、一個課題,一切都因為它是個無理數,也就是無限不循環小數,如果光拿紙和筆計算