我正在尝试创建一个函数,它给出了任何n值的fibonacci序列。然而,在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]
我认为这与整数溢出有关,与矩阵库的限制有关。我不知道如何解决它。请帮帮我。如果这个算法得到改进,我更愿意。
你应该允许使用big-int数字,否则你只能使用默认的63位(+符号位)或np.uint64
(仅大1位):
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]
您应该设置一个明确的dtype
以允许矩阵中更大的数字:
G = np.matrix([[1,1],[1,0]], dtype=np.uint64)
然而,这只是略微提高了标准(如果你的系统甚至没有使用它作为默认值)并且很快就会溢出,你甚至不会轻易注意到它,因为数字不会消极...
@Michael's answer工作得更好。
听起来你正在遇到浮点精度问题。
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