关于Fibonacci数所需的位数

Question

我正在阅读S.DasGupta的算法书.以下是有关第n个Fibonacci数所需位数的文本的文本片段.

如果添加小数字,将加法视为单个计算机步骤是合理的,32位数字表示.但是第n个Fibonacci数约为0.694n位,随着n的增长,这可能远远超过32.对任意大数的算术运算不可能在单个恒定时间步骤中执行.

我的问题是例如,对于Fibonacci数F1 = 1,F2 = 1,F3 = 2,依此类推.然后用上面的公式中的"n"代替,即F1的0.694n约为1,F2约为2位,但对于F3等,上述公式失败.我想我并不理解作者在这里的意思,任何人都可以帮助我理解这一点吗？

谢谢

Answer 1

好,

n              3    4     5     6     7     8
0.694n         2.08 2.78  3.47  4.16  4.86  5.55
F(n)           2    3     5     8     13    21
bits           2    2     3     4     4     5
log(F(n))      1    1.58  2.32  3     3.7   4.39

所需的位数是基数2日志的四舍五入,所以这对我来说足够接近.

值0.694来源于以下事实F(n)是最接近整数(φ ^Ñ)/√5.所以log(F(n))是n * log(phi) - log(sqrt(5)),并且log(phi)是0.694.随着n变得越来越大,log(sqrt(5))四舍五入迅速变得微不足道.