Try   HackMD
tags: 資訊科學教學法作業(2019)

實作報告三

利用隨機函式計算圓周率pi到小數第五位

奇聞軼事

  • 2015年,印度的Rajveer Meena,背到圓周率第7萬小數位,是金氏世界紀錄保持人
  • 2019年,任職谷歌(Google)的日本員工Emma Haruka Iwao,藉由谷歌雲端運算服務的幫助,算出小數點後31.4兆位的圓周率

從小我們都背過圓周率 = 3.141592653,也會用在計算圓的周長或面積,但我們知道圓周率怎麼得到的嗎?

壹、蒙地卡羅求PI原理

一般來說,PI求法就是找半徑為1的圓面積
數學上可用積分法找

𝑥2+𝑦2=1
Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

是否有其他的解法呢?

蒙地卡羅法:不用數值計算方式來解題,而以機率(亂數)來解題的方式

假設正方形邊長為1,圓半徑也為1,那麼圓的面積為

𝐴=𝜋12=𝜋
Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

由上圖可知

14圓的面積為 :
14𝐴=
14𝜋12
=
𝜋4

而正方形面積為:1x1=1
Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

產生分布於0~1 之間的亂數,應當會均勻的分布於正方形之內
而分布於
14
圓內的數量假設為a ,分布於圓外的數量為b,N則是所產生的亂數總數為N=a+b。
Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

那麼其亂數分布數量a與N的比值應與1/4圓面積及正方形面積成正比,於是:

𝜋41=𝑎N

𝜋=4aN

假設我們 N=100,飛鏢射出去命中了78 發,則我們就可以預估圓周率約為:(78/100)*4 = 3.12

如何判斷所產生的點落於圓內?

令亂數產生X與Y兩個數值,如果

𝑥2+𝑦2<=1就是落在圓內。

貳、在Python中求PI

原理:以範圍0~1,先算出

14圓的面積,乘以4後就是
𝜋

算單次
𝜋

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

測試輸出結果

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

多次執行後發現:
1.亂數值運算次數越多,

𝜋越容易逼近正確值
2.亂數值運算次數太大時,運算會很慢

進階算法-算十次求平均值

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

缺點:亂數值運算次數太大時,運算會很慢
解決方法:可將十次步驟分給多台電腦運算

參、蒙特卡羅法缺點

用蒙地卡羅方法近似計算圓周率的先天不足:

  1. 電腦產生的亂數是受到儲存格式的限制的,是離散的,並不能產生連續的任意實數
  2. 將平面分割成一個個網格,在空間不是連續的,由此計算出來的面積與圓或多或少有差距

課程結束