Numpy matrix_power function gives incorrect results for large exponents

Question

I am working on implementing a Fibonacci sequence in Numpy using the Q-Matrix method . Results stop until n = 47. At this point, the matrix_power function returns incorrect results . Any explanation of why this is happening?

 import numpy def fibonacci(n): qmatrix = numpy.matrix([[1, 1], [1, 0]]) (a,b,c,d) = numpy.linalg.matrix_power(qmatrix,n).flatten().tolist()[0] return b print fibonacci(47) # Outputs -1323752223 

Answer 1

If you are going to play with Fibonacci numbers, it’s probably worth sacrificing some speed and using arbitrarily large Python numbers. You can do this by setting your matrix dtype to object .

You also do not need to use the np.matrix object, it is almost always better to stick with regular arrays. And you can extract the corresponding element without converting the array to a list:

 def fibonacci(n): qmatrix = numpy.array([[1, 1], [1, 0]], dtype=object) return numpy.linalg.matrix_power(qmatrix, n)[0, 1]