计算使用该公式在python

Question

我计算使用 （a）一种线性方法的第n个Fibonacci数第n个斐波纳契数，和 （b）中表达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列出了一个良好的执行，但它也列出了基于Lucas数如下算法：

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 

Answer 2

这是因为浮动参与efib浮点运算（）？

是的。在efib你有

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

上的x86-64硬件

和Python floats have about 53 bits of precision，让你运行靠近边缘。

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])