algorithm - 关于斐波那契数所需的位数

Question

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

It is reasonable to treat addition as a single computer step if small numbers are being added, 32-bit numbers say. But the nth Fibonacci number is about 0.694n bits long, and this can far exceed 32 as n grows. Arithmetic operations on arbitrarily large numbers cannot possibly be performed in a single, constant-time step.

我的问题是针对斐波那契数列 F1 = 1、F2 =1、F3=2 等。然后在上面的公式中代入“n”即0.694n对于F1大约是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

所需的位数是四舍五入的 base-2 日志，所以这对我来说已经足够接近了。

值 0.694 是因为 F(n) 是最接近 (φⁿ)/√5 的整数。所以 log(F(n)) 是 n * log(phi) - log(sqrt(5))，并且 log(phi)是 0.694。随着 n 变大，log(sqrt(5)) 和舍入迅速变得无关紧要。