Re: Fibonacci number

[zerodevil (冰心無情)]

※ 引述《tkcn (小安)》之銘言：
: ※ 引述《zerodevil (冰心無情)》之銘言：
: : 我來試著估計一下大數的影響..
: : 由公式解可得 Fn  = (1.618^n - (-0.618)^n) / √5
: :                 ~= 1.618^n / √5
: : 取log之後可看出Fn要用O(n)bit來存
: : n-bit的大數加法複雜度是O(n)
: :            乘法複雜度是O(n^2)   (如果你用FFT之類的火星演算法那另當別論XD)
: 呃...上面那串公式是什麼？
: 該不會又是什麼大學就教的東西吧！
: (老師~我對不起你~Orz)
線性遞迴的公式解
離散之類的可能會講到(?
: : 所以我們回頭看解法1,2,3
: : 解法1需要O(n)次n-bit的大數加法, 沒有乘法, 時間是O(n^2)
: 解法一應該是只有乘法沒有加法吧  :P
我們講的解法一是同一個東西嗎XD

f = new BigInt[n+1]
f[0] = f[1] = 1;
for(int i=2; i<=n; i++) f[i] = f[i-1] + f[i-2];

我指的是這個
: : 解法2,3要O(logn)次n-bit的加法和乘法,      時間是O(n^2 logn)
: : 這樣看來用加的會比較快 (一點點啦.. logn小到可以當常數)
: : 而且簡單好寫XD
: : (edit)
: : 如果估計得緊一點的的話 方法2,3好像也是O(n^2)....
: : 這樣就平手了~_~
--
重回一篇好了 比較不會混亂

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.133.186.66
推 tkcn:哈  那應該是我誤會了，我再研究研究
推 tkcn:噢  我把fabonacci跟factorial搞混了  XDDD
→ tkcn:還有那個公式我現在有印象了
推 SansWord:我有一個問題～fabonacci 不是可以解遞迴式嗎？
→ SansWord:那不就O(1)就可以解出來？
→ zerodevil:算公式解的時候那些加減乘除也是要時間的
推 KanoLoa:小聲偷問，有跟我一樣整串看下來都不懂的人嗎，我要取暖QQ
→ jlovet:遞迴不用多久就會爆炸吧
推 SansWord:公式：1/√5 { [ (1+√5)/2 ]^n - [ (1-√5)/2 ]^n }
→ SansWord:算這個應該constant time吧?
→ tkcn:直接代公式 √5 要怎麼辦?  他可不是分數呀
→ AmosYang:ICPC 進場可以帶紙本的筆記； √5 算個100位印在紙上
→ AmosYang:帶進場，然後用 BigDecimal 硬幹? XD
→ AmosYang:只要你隊上沒有這種 -> http://www.xkcd.com/217/
→ AmosYang:人; rounding error 沒在怕的啦 XD
推 SansWord:按照這個公式，√5 項會被消掉，大可用一個變數替代
推 SansWord:然後偶數次再算出來
先不考慮無理數什麼的
你光算一個數的n次方就至少要O(logn)次乘法了
※ 編輯: zerodevil       來自: 220.133.186.66       (11/06 13:05)
→ AmosYang:(亂入) 如果是做 applied physics 的題目…
→ AmosYang:精確度有到千分之一通常就很夠了 XD (逃)
推 tkcn:我覺得100位應該是完全不夠吧, 要更多就會有大數乘法慢的問題
推 SansWord:也對，後來想到次方也是需要O(logN)