5

I am calculating the n-th fibonacci number using (a) a linear approach, and (b) this expression

Python code:

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

For n > 71 I see that the two functions return different values.

Is this due to floating point arithmetic involved in efib()? If so, is it then advisable to calculate the number using the matrix form?

4

3 回答 3

11

您确实看到了舍入错误。

矩阵形式是更准确和更快的算法。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 开放课件课程的第 3 讲，以对矩阵方法进行很好的分析。

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

>>> 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
于 2012-08-24T06:01:22.040 回答
3

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

是的。你里面efib有

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

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

于 2012-08-24T06:05:13.197 回答
-1

我有一个非常简单的纯 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])
于 2017-02-04T07:14:48.367 回答