Re: [問題] 關於遞迴加快速度的迷思?

看板C_and_CPP作者 (f0VMRgEBA)時間12年前 (2013/09/07 23:15), 編輯推噓1(105)
留言6則, 3人參與, 最新討論串9/10 (看更多)
※ 引述《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)

09/08 09:18, , 1F
Companion Matrix
09/08 09:18, 1F

09/08 09:24, , 2F
然後原po也許是要問calling convention?
09/08 09:24, 2F

09/08 09:29, , 3F
原 PO 問的應該是中間有人提過的呼叫 overhead
09/08 09:29, 3F

09/08 12:02, , 4F
所以c2251393和Feis真的有在推文中各提到一次... :p
09/08 12:02, 4F

09/08 14:53, , 5F
原來如此..我一開始還想說原po也許是想知道一些細節 像是
09/08 14:53, 5F

09/08 14:54, , 6F
09/08 14:54, 6F
文章代碼(AID): #1IAxEEyo (C_and_CPP)
討論串 (同標題文章)
以下文章回應了本文
完整討論串 (本文為第 9 之 10 篇):
文章代碼(AID): #1IAxEEyo (C_and_CPP)