Python斐波那契数没有无限精度？

Question

我正在尝试用Python写一个快速的斐波那契算法，这个算法要能处理非常大的数字，但我总是得到负值，所以我猜可能是没有正确使用长整型？

fibonacci_matrix = numpy.matrix([[1,1],[1,0]])
def fib(n):
  return (fibonacci_matrix**(n-1)) [0,0]

fibonacci_matrix2 = numpy.matrix([[1L,1L],[1L,0L]])
def fib2(n):
  return (fibonacci_matrix2**(n-1)) [0,0]

def fib3(n):
  if n in [1,2]:
    return 1L
  else:
    return long(long(fib2(n-1))+long(fib2(n-2)))

print fib(47)
print fib2(93)
print fib3(95)

这段代码的输出是：

-1323752223
-6246583658587674878
-4953053512429003327

而不是所有斐波那契数应该有的正值。

有人能帮我找出问题吗？或者更好的是，帮我写一个改进版的、高效的、无限准确的斐波那契数列代码？我在网上搜索大多数都是一些非常基础、慢的递归斐波那契算法。

Answer 1

关于“高效且无限精确的斐波那契数列代码”在Python中的实现：像这样的简单递归序列可以通过利用numpy的ufunc的out参数来快速且轻松地计算。选择合适的数据类型可以提高精度。

尽管对于标准种子的斐波那契数来说，在合理的数值范围内并没有太多的数字，你可以利用一些高级的数学特性——这可能对一般人都有兴趣：

>>> a = np.zeros(102, object)
>>> a[1] = 1; a[0] = 0
>>> np.add(a[:-2], a[1:-1], out=a[2:])
array([1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597,
       2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418,
       317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465,
       14930352, 24157817, 39088169, 63245986, 102334155, 165580141,
       ....
       7540113804746346429, 12200160415121876738, 19740274219868223167,
       31940434634990099905, 51680708854858323072, 83621143489848422977,
       135301852344706746049, 218922995834555169026, 354224848179261915075,
       573147844013817084101], dtype=object)
>>> a[100]
354224848179261915075L
>>> a[51]**2 - a[49]**2
354224848179261915075L
>>> 

Answer 2

你遇到了溢出的问题。假设一个长整型（long）是32位的，它能存储的数值范围是 -2^31 .. 2^31 - 1，而第47个斐波那契数是2971215073。

为了准确计算这个值，你需要更大的整数。Python本身就支持大整数，但我觉得numpy可能不支持...

下面是一个纯Python的例子：

def fib4(n):
    x=[1,1]
    for i in xrange(n-2):
        x.append(x[-1]+x[-2])
    return x[-1]    

这样做会强制Python在计算时使用更大的整数值。

Answer 3

你可以通过把数据类型设置为对象，让numpy使用Python的任意精度整数：

>>> fibonacci_matrix = numpy.matrix([[1,1],[1,0]], dtype=object)
>>> def fib(n): return (fibonacci_matrix**(n-1)) [0,0]
>>> 
>>> fib(100)
    354224848179261915075L

不过我不太确定这样做能有多大帮助。通常，如果你想要一个非常快速的递归函数实现，你可以利用一些数学公式来简化计算。例如，使用公式F(2*n) = F(n+1)^2 - F(n-1)^2可以让计算变得更快，达到对数级别的效率。[实际上，维基百科上还有一个更好的这个公式的推广版本。]

你真的需要速度吗？