使用python中的公式计算第n个斐波那契数 [英] Calculating nth fibonacci number using the formulae in python

问题描述

我正在使用
（a）线性方法和
（b）计算第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，我看到两个函数返回不同的值。

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

这是由于efib（）中涉及的浮点运算吗？
如果是，那么是否建议使用矩阵形式来计算数字？

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

推荐答案

您确实看到了舍入错误。

You are indeed seeing rounding errors.

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

The matrix form is the more accurate and much faster algorithm. Literateprograms.org lists a good implementation, but it also lists the following algorithm based on Lucas numbers:

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

看看麻省理工学院开放式课程有关算法的课程的第3课是对矩阵方法的良好分析。

Take a look at Lecture 3 of the MIT Open Courseware course on algorithms for a good analysis of the matrix approach.

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

Both the above algorithm and the matrix approach has Θ(lg n) complexity, just like the naive recursive squaring method you used, yet without the rounding problems. The Lucas numbers approach has the lowest constant cost, making it the faster algorithm (about twice as fast as the matrix approach):

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

这篇关于使用python中的公式计算第n个斐波那契数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！