- 很久以前,曾經 post 了一篇關於 pi 的小數計算程式。一個相當出色的
數學系資訊系學弟(藍永倫,他有個網站在這兒),在前些日子的實驗室會議裡,曾大略講述那個程式背後所用到的數學原理。
- 最近一直忙忙碌碌,被各類「比較有時間急迫性」的瑣事佔據時間,沒有能夠深入地了解(或直接向這位學弟請教)運算式推導程與實作考量。偶而想起來,還是會覺得有些可惜。
- MPH 在幾天前的 post 中,提到「人物專訪產生器」。我也上去玩了一下,對這樣的程式頗感興趣。感興趣的原因,是覺得演算法應該不複雜(大致上,應該就是樣版套用、字串比對與取代 -- 雖然要做得更好,就不是那麼容易),但效果卻頗突出。
- 事實上,我覺得背後隱隱還有「人的閱讀方式與文字魅力」這樣的大道理在,但可惜自己並沒有足夠能力來深究。如果有時間,自己是頗想寫一個這樣的程式來玩玩。
- 覺得實驗室在理論與實際間的取捨饒富趣味。項老師的理論背景非常強,但卻一直希望實驗室能夠做出一些「實際有用的系統」。
- 有趣的地方是,即使這樣的企圖已經持續了十年,即使實驗室有著優秀的資訊人才、即使實驗室在經費上一直供應無缺,但... 在陳必衷的「蝴蝶生態面面觀」之後,似乎就沒有生產出什麼像樣些的系統。(我覺得它至今也依然像是實驗性質的系統:許多蝴蝶只有圖檔與名稱,沒有更深入的介紹。)
- 我目前是認為,許多開發效率上的問題,應該與流程有頗大的關係。而思考、感受理論與實際間的差異、並參考軟體工程的理念,一直都是我相當感興趣的主題。
後記:我弄錯了,永倫是「資訊系」,非「數學系」的學弟。
11 則留言:
>覺得實驗室在理論與實際間的取捨「饒富趣味」。
真是「饒富趣味」的說法啊。
嗯... MPH 的回答也真有趣味 :)
其實,感覺自己不懂、內容卻有其奇妙處,本身就是一種趣味啦~
上次講得太匆忙,忘了舉例子,不然大家一定聽得懂... 舉例來說,不要算太多項,先這樣好了:
π ≒ 2 + 1/3( 2 + 2/5( 2 + 3/7(2)))
如果是筆,會怎麼算?順序一定是由內而外。
2 + 1/3( 2 + 2/5( 2 + 3/7(2)))
= 2 + 1/3( 2 + 2/5( 2 + (0 + 6/7)))
= 2 + 1/3( 2 + 2/5( 2 + (0))) + [1/3(2/5(6/7))] /* 把誤差拉出來放到方括號中 */
= 2 + 1/3(2 + 0 + 4/5) + [1/3(2/5(6/7))]
= 2 + 1/3(2) + [1/3(2/5(6/7)) + 1/3(4/5)]
= 2 + 0 + 2/3 + [1/3(4/5 + 2/5(6/7))]
= 2 + [2/3 + 1/3(4/5 + 2/5(6/7))]
出來個位數 2
再來看方括號裡的東西,這次要算小數點以下第一位:
2/3 + 1/3(4/5 + 2/5(6/7))
= 2/3 + 1/3(4/5 + 2/5(0.8 + 3/70))
= 2/3 + 1/3(4/5 + 2/5(0.8)) + [1/3(2/5(0.3/7))]
= 2/3 + 1/3(0.8 + 0.3 + 0.1/5) + [1/3(2/5(0.3/7))]
= 2/3 + 1/3(0.8 + 0.3) + [1/3(0.1/5 + 2/5(0.3/7))]
= 2/3 + 0.3 + 0.2/3 + [1/3(0.1/5 + 2/5(0.3/7))]
= 2/3 + 0.3 + [0.2/3 + 1/3(0.1/5 + 2/5(0.3/7))]
= 0.9 + 0.2/3 + [0.2/3 + 1/3(0.1/5 + 2/5(0.3/7))]
= 0.9 + [0.4/3 + 1/3(0.1/5 + 2/5(0.3/7))]
小數點第一位出來了(好累)
然後在適當的地方乘 10 除 10 就可以讓整個運算變成整數運算...
btw, 我其實是資訊系畢業的 orz
啊,竟然麻煩永倫回了一個「這麼長」的運算範例...
這下子,再繼續推託,就很不好意思了...(其實,或許是自己已經對數學式的推導產生排拒感,所以會找藉口來推託吧?)
嗯... 我覺得我的疑問,可能比較是在於細節吧?例如,在於「誤差」的推導(或者說,何時會產生進位、何時可以捨棄的一般式推導 -- 總覺得頗為複雜)。
像是永倫在樓上舉的這個小例子,產生的第一個數字是 2,第一個小數位數是 9。那麼,需要多少項(或者,第幾項之後就不可能產生進位)才能產生正確的前兩位數 (3.1) 呢?
「誤差的推導」要說清楚不容易,不過要回答「需要多少項(或者,第幾項之後就不可能產生進位)才能產生正確的前兩位數 (3.1) 呢?」這個問題卻沒那麼困難。
把級數展開來:
π = 2 + 1/3( 2 + 2/5( 2 + 3/7( ... ( 2 + k/(2k+1)(...)))))
= 2 + 1/3 * 2 + 1/3 * 2/5 * 2 + 1/3 * 2/5 * 3/7 * 2 + ... + ∏(k/2k+1) * 2+ ...
第 k 項就是(假設從第 0 項開始)
(1/3 * 2/5 * 3/7 * ... * k/2k+1) * 2
< 1/2 * 1/2 * 1/2 * ... * 1/2 *2
< 1/2^(k-1)
也就是說做到第 k 項,誤差會小於 1/2^(k-1)。
當然,「誤差小於 0.001」並不代表小數點以下 2 位就是對的,我想杜老大的困惑應該在這裡,這的確是個問題,級數和求 π 的方法應該沒辦法解決這點。不過實作上其實只要加到第 k 項時看最後的尾巴是不是連續的 9 ,如果不是我們就可以斷言小數點以下 2 位是正確的,如果是那就得多加幾個 term 。
要小數點兩位以下正確,希望誤差小於 0.001 = 10^-3 ≒ 2^-10
所以做 12 項應該足夠,事實上 6 項就已經到 3.12 了。
差不多蜥蜴,文章還寫是數學系學弟 :P
嗯,謝謝永倫的回答(原先應該就是 precision 在實作上的問題),這樣我就可以省下許多時間啦!
貓:我本來是想留著自己的錯誤,所以把「錯誤更正」放在「後記」裡啊。
哎,看來大家都沒有力氣看到 post 最後的那些內容... XD 還是直接更動本文好了...
有看到 PS 啊,只是又不是印刷書本的勘誤表,前面寫錯了,後面用 PS 更正,真的很奇怪耶。
要留修改歷史,可以用刪除線畫掉再加上新的。
嗯,在貓的留言後,我的確就是用「刪改線」槓掉錯誤的資訊,然後寫一份新的在後頭。
只是,這樣子看起來很醜就是了...
張貼留言