※ 引述《kc655039 (NNN  )》之銘言：
: 如果以2^32次方來當做數值系統,也就是2的三十二次方進位的話
: 那麼FIB(2^32)需要用到幾位
: fib是fibonacci
fibonacci 的通項是
1 1 + sqrt(5) n 1 - sqrt(5) n
------- [ ( ----------- ) - ( ----------- ) ]
sqrt(5) 2 2
後面 n 很大時很小, 大約是
1 1 + sqrt(5) n
------- ( ----------- )
sqrt(5) 2
對 2 取對數
1
n lg [ 1 + sqrt(5) ] - n - --- lg 5
2
大約是 0.7 n - 1.16, 這是二進制位數
用 2^32 次方進位則除以 32, 把 n = 2^32 代入
大約是 0.7 * 2^27 = 93952410 位吧...
fibonacci 相關資料可參考 http://mathworld.wolfram.com/FibonacciNumber.html
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.20