斐波那契数列 92 后的否定答案 python

Question

我正在尝试创建一个函数，为我提供任何 n 值的斐波那契数列。但是，在 n = 92 之后，我得到的答案不正确。

eg. For n = 93
Expected output = 12200160415121876738
Actual Output = -6246583658587674878

我的代码如下：

import numpy as np
def Power(M, n):
         if not n:
                 return 1
         elif n % 2:
                 return M*Power(M, n-1)
         else:
                 sqrt = Power(M, n//2)
                 return sqrt**2

  def _fib(n):
     G = np.matrix([[1,1],[1,0]])
     F = Power(G, n)
     return F[0,1]

我觉得和矩阵库的限制有关的整数溢出有关系。我不确定如何修复它。请帮帮我。如果这个算法得到改进，我会更喜欢。

使用的算法：

Answer 1

听起来您遇到了浮点精度问题。

Python 3 的整数是任意精度的，所以你可以只使用它们和 lru_cache 来记忆：

from functools import lru_cache


@lru_cache()
def fib(n):
    if n <= 1:
        return 1
    return fib(n - 2) + fib(n - 1)


for x in range(1, 95):
    print(x, fib(x - 1))

产出

1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34
10 55
11 89
12 144
13 233
14 377
15 610
16 987
...
92 7540113804746346429
93 12200160415121876738
94 19740274219868223167

Answer 2

您应该明确设置 dtype 以允许矩阵中的数字更大：

G = np.matrix([[1,1],[1,0]], dtype=np.uint64)

但是，这只会稍微提高标准（如果您的系统甚至没有将其用作默认设置）并且很快也会溢出，您甚至不会那么容易地注意到它，因为数字不会变成负数...

效果更好。

Answer 3

你应该允许大整数，否则你会被默认的 63 位（+符号位）或只大 1 位的 np.uint64 限制：

import numpy as np
def Power(M, n):
   if not n:
      # Original 'return 1' does not work with n=0
      return np.identity(2, dtype=object)
   elif n % 2:
      return M*Power(M, n-1)
   else:
      sqrt = Power(M, n//2)
      return sqrt**2

def fib(n):
     # This allows for big-int
     G = np.matrix([[1,1],[1,0]], dtype=object)
     F = Power(G, n)
     return F[0,1]

斐波那契数列 92 后的否定答案 python

fibonacci sequence negative answer after 92 python

python

numpy

fibonacci