Python 中的大斐波那契数不准确

Question

我目前正在实现这个简单的代码，试图使用 Python 2.7:

找到斐波那契数列的第 n 个元素

import numpy as np

def fib(n):
        F = np.empty(n+2) 
        F[1] = 1
        F[0] = 0
        for i in range(2,n+1):
            F[i]=F[i-1]+F[i-2]
        return int(F[n])

对于 F < 79 这很好用，但在那之后我得到了错误的数字。例如，根据 wolfram alpha F79 应该等于 14472334024676221，但是 fib(100) 给了我 14472334024676220。我认为这可能是由 python 处理整数的方式引起的，但我不知道到底是什么问题是。非常感谢任何帮助！

Answer 1

numpy 数组的默认数据类型是 depending on architecture 64（或 32）位整数。

pure python 会让你有任意长的整数； numpy 没有。

所以这更像是 numpy 处理整数的方式；纯 python 就可以了。

Answer 2

作为对 hiro 主角 先前回答的补充，请注意，如果需要使用 Numpy，您可以通过替换以下内容轻松解决您的问题：

F = np.empty(n+2)

和

F = np.empty(n+2, dtype=object)

但它只会将计算转回纯 Python。

Answer 3

Python 将在这里完美地处理整数。的确，那就是python的美。另一方面，numpy 引入了丑陋，恰好完全没有必要，而且可能会让你慢下来。您的实施还需要更多 space。 Python 允许您编写美观、可读的代码。这是 Raymond Hettinger 在 Python:

中迭代斐波那契的规范实现

def fib(n):
    x, y = 0, 1
    for _ in range(n):
        x, y = y, x + y
    return x

即O(n)时间和常数space。它美观、可读且简洁。只要您有足够的内存将数字存储在计算机上，它也会为您提供正确的整数。学会在合适的工具时使用 numpy，同样重要的是，学会在不合适的时候不使用它。

Answer 4

除非你想生成一个包含 Fn 之前所有斐波那契数列的列表，否则不需要使用列表、numpy 或其他类似的东西，一个简单的循环和 2 个变量就足够了，因为你只需要知道前两个值

def fib(n):
   Fk, Fk1 = 0, 1
   for _ in range(n):
      Fk, Fk1 = Fk1, Fk+Fk1
   return Fk

当然，还有更好的方法可以利用 Fibonacci numbers, with those we know that there is a matrix 的数学特性来给出正确的结果

import numpy

def fib_matrix(n):
    mat = numpy.matrix( [[1,1],[1,0]], dtype=object) ** n
    return mat[0,1]

我假设他们有一个优化矩阵 exponentiation 使它比以前的方法更有效。

使用基础 Lucas sequence 的属性可以在没有矩阵的情况下完成，并且与通过平方求幂和使用与另一个相同数量的变量同样有效，但这有点难乍一看不像第一个例子，因为除了第二个例子，它还需要更多的数学知识。

接近的形式，黄金比例的形式，会给你更快的结果，但是因为使用浮点运算，所以有不准确的风险。

Python 中的大斐波那契数不准确

Inaccurate Large Fibonacci Numbers in Python

python

fibonacci