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

Question

我正在使用线性方法和this表达式计算第n个斐波那契数。

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()中涉及浮点运算吗？如果是，那么使用矩阵形式计算是否明智？

- Sumit

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

请查看MIT开放式课程算法课程的第三讲，以获取有关矩阵方法的良好分析。

与您使用的朴素递归平方方法一样，上述算法和矩阵方法都具有Θ(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

- Martijn Pieters

Answer 2

这是由于efib()中涉及浮点运算吗？

是的，是由于这个原因。在efib函数内部，您有

>>> log(x**72)/log(2)
49.98541778140445

在 x86-64 硬件上，Python 浮点数大约有 53 位的精度，因此你正在接近边缘。

- poolie

Answer 3

我有一个非常简单，纯粹的 Python 代码...

def fibonum(n):   # Give the nth fibonacci number
    x=[0,1]
    for i in range(2,n):
        x.append(x[i-2]+x[i-1])
    print(x[n-1])

- shahri23

---

不需要使用.append在内存中构建列表。您只需使用两个变量--请参见OP中的lfib定义。 - peterhurford