作者AmosYang (LetMeGoogleThatForYou)
看板java
標題Fibonacci number
時間Wed Nov 4 13:05:00 2009
: → jlovet:嗯,我覺得不知道fibonacci 可以在log N算出來的人蠻可憐的 11/03 14:48
: → SansWord:好跳tone的感覺..fibonacci怎麼樣在log N算出來？(好奇) 11/04 02:30
: 推 AmosYang:大學linear algebra應該會教到…可以推出 F(2n)=F(n)+F(n 11/04 09:02
: → AmosYang:重推一次: F(2n-1) = F(n)^2+F(n-1)^2 11/04 09:04
: → AmosYang:hmm...其實 wikipedia 上有; search for "matrix form" 11/04 09:06
: → AmosYang: http://en.wikipedia.org/wiki/Fibonacci_number 11/04 09:07
: → tkcn:http://www.csie.ntnu.edu.tw/~u91029/Q-matrix.html 11/04 10:43
剛胡思亂想了一下…發現件蠻有趣的事
如果把 BigInteger 的乘法與加法的代價也算進來，
tkcn 指出的 Q-matrix 算法不見得佔優勢…以下是我的分析
解法一: 普通解法，開一個 array, 從 F0 開始填，一路填到 Fn
演算法本身是 O(n); 實際上做了 O(n) 次 BigInteger 的加法
這解法的好處是簡單易寫，且算過一次就不用再算，以後可以直接查表
解法二: Q-matrix
演算法
號稱為 O(log n)
之所以用號稱這字眼是因為我自己還沒有推演求證過
但 2x2 的 matrix 相乘事實上做了 8 次 BigInteger 乘法及 4 次 BigInteger 加法
matrix 相乘 n 次就是做了 8n 次 BigInteger 乘法及 4n 次 BigInteger 加法
當然，matrix 相乘還可以再優化，不過，我覺得在比賽的壓力下實在很難辦到 XD
smartboy 那種神人可以，我是辦不到的 XD
解法二稍為在 matrix 裡加工一下，一樣可以存放已經算過的值
解法三為解法一的變型
解法一是架構在
F0 = 1
F1 = 1
Fn = F(n-1) + F(n-2)
之上
解法三則是架構在
F0 = 1
F1 = 1
F(2n-1) = F(n)^2 + F(n-1)^2
F(2n) = (2 * F(n-1) + F(n)) * F(n) = (F(n-1) + F(n-1) + F(n)) * F(n)
之上
一樣開一個 array 存放算過的值
演算法
看起來是 O(log n)
這部分我還沒有仔細去推演，但用實際數值算出來的結果，
F100 要算 16 次; 而 F10000 要算 33 次，我就當他是 O(log n) 了 XD
F100 要做 21 次 BigInteger 加法及 21 次 BigInteger 乘法
F10000 要做 47 次 BigInteger 加法及 46 次 BigInteger 乘法
解法三的寫法與解法一一樣很直接，然而，這個解法是要看運氣的，
因為坦白說在比賽的現場壓力下我是沒辦法從解法二一路推演到解法三 XD
與其去推演這個不如去用解法一硬幹 XD
總結，假設要求 F10000
BigInteger.Add BigInteger.Multiply
解法一 O(n) 10000 0
解法二 O(log n) 40000 80000
解法三 O(log n) 47 46
這樣子比較，個人感覺上解法二有點吃力不討好
不過，這個分析還沒考慮到 BigInteger 實做的方式及大小數字計算的速度差異…
待有心人三種解法都寫一次，開 profiler 直接去量時間吧... XD
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 65.87.177.87
突然想到，其實在 2x2 的 matrix multiplication 運算裡，
可以很簡單地用 dynamic programming 來優化
所以事實上解法二沒有我想像的那麼糟…
待別的有心人來為解法二平反吧
Z..z..z...
※ 編輯: AmosYang 來自: 65.87.177.87 (11/04 13:11)
突然又再想到…解法二的 matrix multiplication 用最簡單的 A^m * A^n = A^(m+n)
優化後，就會變成
BigInteger.Add BigInteger.Multiply
解法一 O(n) 10000 0
解法二 O(log n) 400 800
解法三 O(log n) 47 46
不過，這個表格只是比較 "求一個數字" 的代價
解法二、三看起來代價比較小，也只是取巧
真的碰上測試資料要 F0 到 Fn 通通問一遍的，解法二、三大概也佔不了什麼便宜 XD
最後…還是岸和田那句老話: 實驗最準!! 不用代入公式!! 也不用修正誤差!! XD
Zzz...
※ 編輯: AmosYang 來自: 65.87.177.87 (11/04 13:24)
快要睡著時再突然想到…修正解法二的數字…
之前的 400 與 800 毫無根據…不知道為什麼會那樣想…
BigInteger.Add BigInteger.Multiply
解法一 O(n) n=10000 0
解法二 O(log n) (4 log n / log 2) = 53 (8 log n / log 2) = 106
解法三 O(log n) 47 46
至此…其實解法二、三沒差多少了…
今夜獨角戲到此結束…謝謝收看… Zzz...
※ 編輯: AmosYang 來自: 65.87.177.87 (11/04 13:52)
※ 編輯: AmosYang 來自: 65.87.177.87 (11/04 13:55)
推 tkcn:題外話問一下，你也是用 Java 寫 ACM 嗎? XD 11/04 14:24
我一開始是用 C++ ，後來被 BigInteger 引去 Java
再後來在 TopCoder.com 上見識到 C# 的流氓之處，就再轉 C# 了
現在則是用嘴吧寫… XD
→ jlovet:你確定他需要乘八次....? 11/04 15:55
剛有偷看底下的回文…的確不需要乘到 8 次，多謝指教 :D
※ 編輯: AmosYang 來自: 65.87.177.87 (11/05 10:25)
推 petertc:糟了我不知道 11/05 19:36