Numpy矩阵求幂给出负值

Question

我想NumPy在Fibonacci问题中使用它,因为它在矩阵乘法中的效率.您知道有一种方法可以使用矩阵查找斐波纳契数[[1, 1], [1, 0]].

我写了一些非常简单的代码但是在增加之后n,矩阵开始给出负数.

import numpy
def fib(n):
    return (numpy.matrix("1 1; 1 0")**n).item(1)

print fib(90)
# Gives -1581614984

这可能是什么原因？

注意: linalg.matrix_power也给出负值.

注2:我尝试了从0到100的数字.它在47之后开始给出负值.这是一个大的整数问题,因为NumPy是用C编码的吗？如果是这样,我怎么能解决这个问题？

编辑:使用常规python list矩阵linalg.matrix_power也给出了负面结果.另外,我要补充一点,47之后并非所有结果都是负数,而是随机发生.

Edit2:我尝试使用@ AlbertoGarcia-Raboso建议的方法.它解决了负数问题,但是出现了另一个问题.它给出了-5.168070885485832e+19我需要的答案-51680708854858323072L.所以我尝试使用int(),它将其转换为L,但现在似乎答案是不正确的,因为精度损失.

Answer 1

您看到负值出现的原因是因为NumPy默认使用np.int32dtype作为矩阵.

这个dtype可以表示的最大正整数是2 ³¹ -1,即2147483647.不幸的是,这小于第47个斐波那契数,2971215073.结果溢出导致负数出现:

>>> np.int32(2971215073)
-1323752223

使用更大的整数类型(例如np.int64)会解决这个问题,但只能暂时解决:如果你不断要求更大和更大的Fibonacci数字,你仍会遇到问题.

唯一可靠的解决方法是使用无限大小的整数类型,例如Python的int类型.为此,请将矩阵修改为以下np.object类型:

def fib_2(n):
    return (np.matrix("1 1; 1 0", dtype=np.object)**n).item(1)

该np.object类型允许矩阵或数组保存任何本机Python类型的混合.从本质上讲,矩阵现在的行为类似于Python列表,而不仅仅是持有机器类型,而是简单地包含指向内存中整数对象的指针.现在,Python整数将用于计算Fibonacci数,溢出不是问题.

>>> fib_2(300)
222232244629420445529739893461909967206666939096499764990979600

这种灵活性是以降低性能为代价的:NumPy的速度源于整数/浮点类型的直接存储,可由硬件操纵.