→ DJWS:Companion Matrix 09/08 09:18
推 DJWS:然後原po也許是要問calling convention? 09/08 09:24
→ LPH66:原 PO 問的應該是中間有人提過的呼叫 overhead 09/08 09:29
→ Schottky:所以c2251393和Feis真的有在推文中各提到一次... :p 09/08 12:02
→ DJWS:原來如此..我一開始還想說原po也許是想知道一些細節 像是 09/08 14:53
※ 引述《Schottky (Schottky)》之銘言：
: 那麼 Fibonacci 整數數列本身也是可以用類似的二分再二分法去計算的,
: 我一直在奇怪, 前面怎麼都沒有人提到過... 可能是目前用到的 n 太小的關係...
: 令函數 f(n) = (a, b, c, d) 傳回值是四個係數, 代表以 F[0]=x, F[1]=y 開頭的
: Fibonacci 數列, 其最後兩項為 F[n-1]=ax+by, F[n]=cx+dy,
: 將兩條數列接起來, 則可推得 f(2n-1) = ((a^2+bc),(ab+bd),(ac+cd),(bc+d^2))
: 所以我們只需要把數列切成等長的兩半計算, 算完再用上面的公式接起來即可...
其實應該是有提到過, 只是型式不一樣而已...
就是這條推文
: 推 c2251393:是說可以構造矩陣((1, 1),(1, 0))來加速www 09/06 23:48
這個做法的原理是
[1 1] . [y] = [x+y]
[1 0] [x] [ y ]
所以我們有
[1 1]^n . [f(1)] = [f(n+1)]
[1 0] [f(0)] [ f(n) ]
那若我們記
[1 1]^n = [d c] (這樣就有 [1 1]^n [y] = [d c] [y] = [cx+dy] )
[1 0] [b a] [1 0] [x] [b a] [x] [ax+by]
則
[1 1]^2n = [d c]^2 = [d^2+cb dc+ca ]
[1 0] [b a] [db+ba cb+a^2]
這個矩陣正等同於你的遞迴式
因此 "對半"做矩陣次方的做法便等同於你的"將數列切對半"
這兩個做法是似二而實一的
--
'You've sort of made up for it tonight,' said Harry. 'Getting the
sword. Finishing the Horcrux. Saving my life.'
'That makes me sound a lot cooler then I was,' Ron mumbled.
'Stuff like that always sounds cooler then it really was,' said
Harry. 'I've been trying to tell you that for years.'
-- Harry Potter and the Deathly Hollows, P.308
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.41.7.174
※ 編輯: LPH66 來自: 114.41.7.174 (09/08 07:15)