星期六, 1月 06, 2007

雜記:幾件感興趣的事

這一陣子,有幾件令自己還頗感興趣的事:
  • 很久以前,曾經 post 了一篇關於 pi 的小數計算程式。一個相當出色的數學系資訊系學弟(藍永倫,他有個網站在這兒),在前些日子的實驗室會議裡,曾大略講述那個程式背後所用到的數學原理。
  • 最近一直忙忙碌碌,被各類「比較有時間急迫性」的瑣事佔據時間,沒有能夠深入地了解(或直接向這位學弟請教)運算式推導程與實作考量。偶而想起來,還是會覺得有些可惜。
  • MPH 在幾天前的 post 中,提到「人物專訪產生器」。我也上去玩了一下,對這樣的程式頗感興趣。感興趣的原因,是覺得演算法應該不複雜(大致上,應該就是樣版套用、字串比對與取代 -- 雖然要做得更好,就不是那麼容易),但效果卻頗突出。
  • 事實上,我覺得背後隱隱還有「人的閱讀方式與文字魅力」這樣的大道理在,但可惜自己並沒有足夠能力來深究。如果有時間,自己是頗想寫一個這樣的程式來玩玩。
  • 覺得實驗室在理論與實際間的取捨饒富趣味。項老師的理論背景非常強,但卻一直希望實驗室能夠做出一些「實際有用的系統」。
  • 有趣的地方是,即使這樣的企圖已經持續了十年,即使實驗室有著優秀的資訊人才、即使實驗室在經費上一直供應無缺,但... 在陳必衷的「蝴蝶生態面面觀」之後,似乎就沒有生產出什麼像樣些的系統。(我覺得它至今也依然像是實驗性質的系統:許多蝴蝶只有圖檔與名稱,沒有更深入的介紹。)

  • 我目前是認為,許多開發效率上的問題,應該與流程有頗大的關係。而思考、感受理論與實際間的差異、並參考軟體工程的理念,一直都是我相當感興趣的主題。
只是,能不能找出時間來想想、做做這些事?自己卻實在沒有把握。然而,也正因為對「是否能夠更進一步去探究」沒有把握,所以就把先它們當作「隨手雜記」吧。

後記:我弄錯了,永倫是「資訊系」,非「數學系」的學弟。

11 則留言:

  1. >覺得實驗室在理論與實際間的取捨「饒富趣味」。
    真是「饒富趣味」的說法啊。

    回覆刪除
  2. 嗯... MPH 的回答也真有趣味 :)

    其實,感覺自己不懂、內容卻有其奇妙處,本身就是一種趣味啦~

    回覆刪除
  3. 上次講得太匆忙,忘了舉例子,不然大家一定聽得懂... 舉例來說,不要算太多項,先這樣好了:

    π ≒ 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

    回覆刪除
  4. 啊,竟然麻煩永倫回了一個「這麼長」的運算範例...

    這下子,再繼續推託,就很不好意思了...(其實,或許是自己已經對數學式的推導產生排拒感,所以會找藉口來推託吧?)

    回覆刪除
  5. 嗯... 我覺得我的疑問,可能比較是在於細節吧?例如,在於「誤差」的推導(或者說,何時會產生進位、何時可以捨棄的一般式推導 -- 總覺得頗為複雜)。

    像是永倫在樓上舉的這個小例子,產生的第一個數字是 2,第一個小數位數是 9。那麼,需要多少項(或者,第幾項之後就不可能產生進位)才能產生正確的前兩位數 (3.1) 呢?

    回覆刪除
  6. 「誤差的推導」要說清楚不容易,不過要回答「需要多少項(或者,第幾項之後就不可能產生進位)才能產生正確的前兩位數 (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 了。

    回覆刪除
  7. 差不多蜥蜴,文章還寫是數學系學弟 :P

    回覆刪除
  8. 嗯,謝謝永倫的回答(原先應該就是 precision 在實作上的問題),這樣我就可以省下許多時間啦!

    貓:我本來是想留著自己的錯誤,所以把「錯誤更正」放在「後記」裡啊。

    哎,看來大家都沒有力氣看到 post 最後的那些內容... XD 還是直接更動本文好了...

    回覆刪除
  9. 有看到 PS 啊,只是又不是印刷書本的勘誤表,前面寫錯了,後面用 PS 更正,真的很奇怪耶。

    回覆刪除
  10. 要留修改歷史,可以用刪除線畫掉再加上新的。

    回覆刪除
  11. 嗯,在貓的留言後,我的確就是用「刪改線」槓掉錯誤的資訊,然後寫一份新的在後頭。

    只是,這樣子看起來很醜就是了...

    回覆刪除