Numpy 矩阵求幂给出负值

Question

我想在斐波那契问题中使用 NumPy，因为它在矩阵乘法方面的效率很高。您知道有一种使用矩阵 [[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 建议的方法。它解决了负数问题，但是出现了另一个问题。它在我需要 -51680708854858323072L 的地方给出了 -5.168070885485832e+19 的答案。所以我尝试使用 int()，它把它转换成 L，但现在看起来答案不正确，因为精度损失。

Answer 1

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

此 dtype 可以表示的最大正整数是 2³¹-1，即 2147483647。不幸的是，这小于第 47 个斐波那契数 2971215073。由此产生的溢出导致出现负数：

>>> np.int32(2971215073)
-1323752223

使用更大的整数类型（如 np.int64）可以解决这个问题，但只是暂时的：如果你继续要求越来越大的斐波那契数，你仍然运行会遇到问题。

唯一确定的解决方法是使用无限大小的整数类型，例如 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 现在斐波那契数列的计算将使用整数，溢出不是问题。

>>> fib_2(300)
222232244629420445529739893461909967206666939096499764990979600

这种灵活性是以降低性能为代价的：NumPy 的速度源于直接存储 integer/float 类型，可以由您的硬件操作。

Numpy 矩阵求幂给出负值

Numpy matrix exponentiation gives negative value

python

numpy

matrix

fibonacci

exponentiation