python - 使用python中的公式计算第n个斐波那契数

Question

我正在使用以下方法计算第 n 个斐波那契数(a) 线性方法，以及(二) this表达

Python代码:

'Different implementations for computing the n-th fibonacci number'

def lfib(n):
    'Find the n-th fibonacci number iteratively'
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return a

def efib(n):
    'Compute the n-th fibonacci number using the formulae'
    from math import sqrt, floor
    x = (1 + sqrt(5))/2
    return long(floor((x**n)/sqrt(5) + 0.5))


if __name__ == '__main__':
  for i in range(60,80):
    if lfib(i) != efib(i):
      print i, "lfib:", lfib(i)
      print "   efib:", efib(i)

对于 n > 71，我看到这两个函数返回不同的值。

这是由于 efib() 中涉及的浮点运算吗？如果是这样，那么建议使用 matrix form 来计算数字吗？ ？

Answer 1

您确实看到了舍入错误。

矩阵形式是更准确的和更快的算法。 Literateprograms.org列出了一个很好的实现，但它也列出了以下基于卢卡斯数的算法:

def powLF(n):
    if n == 1:     return (1, 1)
    L, F = powLF(n//2)
    L, F = (L**2 + 5*F**2) >> 1, L*F
    if n & 1:
        return ((L + 5*F)>>1, (L + F) >>1)
    else:
        return (L, F)

def fib(n):
    if n & 1:
        return powLF(n)[1]
    else:
        L, F = powLF(n // 2)
        return L * F

看看Lecture 3 of the MIT Open Courseware course on algorithms以便更好地分析矩阵方法。

上述算法和矩阵方法都具有 Θ(lg n) 复杂度，就像您使用的朴素递归平方方法一样，但没有舍入问题。 Lucas 数方法具有最低的常数成本，使其成为更快的算法(大约是矩阵方法的两倍):

>>> timeit.timeit('fib(1000)', 'from __main__ import fibM as fib', number=10000)
0.40711593627929688
>>> timeit.timeit('fib(1000)', 'from __main__ import fibL as fib', number=10000)
0.20211100578308105