※ 引述《AmosYang (LetMeGoogleThatForYou)》之銘言：
: 解法三則是架構在
: 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)
: 之上
第一次看到這公式 (以前線代沒認真學 囧)
檢查了一下你的公式，
F0, F1 應該是這樣才對
F0 = 0
F1 = 1
: 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
實作了一下解法三 (Top-Down)，數字和你寫的一樣。
來說一下解法 2 的好處吧，
我是用 Bottom-Up 寫的
(1) 首先
T(1) = [ 0 1 ] // 放在 array[0]
[ 1 1 ]
接下來一個迴圈算出
T(2) = T(1) * T(1) // * 代表矩陣乘法, 放 array[1]
T(4) = T(2) * T(2) // 放 array[2]
...
上面這個動作只需要算一次
(2) 接下來要算 n=10000 時
就可以輕鬆搞定:
Matrix result = [1, 1]; // [ f(0), f(1) ]
for(int i=0;i<31;i++)
if( ((n>>i) & 1) == 1 ) // 判斷第 i 位元是否為 1
result = array[i] * result;
一個 2x2 的矩陣乘法需要 8 個乘法與 4 個加法，
因為 2^13 <= 10000 < 2^14
所以我第一個迴圈就只算到 13 就好。 // 通常我會算到 31
然後因為 10000 的 bit-pattrns 有 4 個 1，
所以需要用到四次的 (2x2 矩陣 乘 2x1 矩陣)，
這種情形乘法需用 4 次 ，加法 2 次。
結論，
乘法次數: 13*8 + 4*4 = 120
加法次數: 13*4 + 4*2 = 60
理論上，只算 n=10000 時，次數應該會更少，
我猜測可能就是你的估計值，
不過我現在的這種作法，
在 n 為其它值時，
只需要重複步驟二即可。
另一個好處就是 code 很短
矩陣相乘: 3 行
步驟(1): 2 行
步驟(2): 3 行
(上面省略了宣告)
---
再補充一下好了，
步驟 (1) 矩陣相乘時，被乘數和乘數都是同一個矩陣
其實只需要用到 7 次乘法。
---
能不用大腦寫程式是件很開心的事情..XD
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.122.183.196
※ 編輯: tkcn 來自: 140.122.183.196 (11/04 16:12)
※ 編輯: tkcn 來自: 61.217.194.110 (11/04 19:09)
→
11/05 10:42, , 1F
11/05 10:42, 1F
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 2 之 7 篇)：