8

I wanted to use NumPy in a Fibonacci question because of its efficiency in matrix multiplication. You know that there is a method for finding Fibonacci numbers with the matrix [[1, 1], [1, 0]].

Fibo

I wrote some very simple code but after increasing n, the matrix is starting to give negative numbers.

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

print fib(90)
# Gives -1581614984

What could be the reason for this?

Note: linalg.matrix_power also gives negative values.

Note2: I tried numbers from 0 to 100. It starts to give negative values after 47. Is it a large integer issue because NumPy is coded in C ? If so, how could I solve this ?

Edit: Using regular python list matrix with linalg.matrix_power also gave negative results. Also let me add that not all results are negative after 47, it occurs randomly.

Edit2: I tried using the method @AlbertoGarcia-Raboso suggested. It resolved the negative number problem, however another issues occured. It gives the answer as -5.168070885485832e+19 where I need -51680708854858323072L. So I tried using int(), it converted it to L, but now it seems the answer is incorrect because of a loss in precision.

Community
  • 1
  • 1
Rockybilly
  • 2,938
  • 1
  • 13
  • 38
  • Your code results in `2880067194370816120` for me (numpy1.10.4). What numpy version do you have? – mgilson Sep 20 '16 at 19:39
  • Try adding dots after your `1`s and `0`s to make a matrix of floats: `numpy.matrix("1. 1.; 1. 0.")`. – Alicia Garcia-Raboso Sep 20 '16 at 19:40
  • 1
    @mgilson I used `numpy.__version__` which gave `1.11.1` – Rockybilly Sep 20 '16 at 19:41
  • 2
    It sounds like you have a 32 bit build of NumPy. `fib(47)` should be 2971215073 which is slightly too big for a signed 32 bit integer. – Alex Riley Sep 20 '16 at 19:44
  • Print out the `dtype` of the matrix you create in `fib(n)` before exponentiating. If it is `int32`, then you are overflowing the maximum 32bit integer (2147483647). You could solve this by specifically stating the dtype in matrix creation, e.g. `numpy.matrix("1 1; 1 0", dtype=np.int64)` if your OS is 64 bit. – wflynny Sep 20 '16 at 19:44
  • 1
    @ajcr I used this http://stackoverflow.com/questions/33553549/do-i-have-numpy-32-bit-or-64-bit to check my `NumPy`. It says 64-bit. – Rockybilly Sep 20 '16 at 19:47
  • Try `np.int64`. It should extend the range of working values. But you'll still end up with overflow issues. Python scalars can be extended precision longs, but not `numpy` integer arrays. – hpaulj Sep 20 '16 at 19:48
  • @Rockybilly: ah ok. But regardless of this, it looks like NumPy is defaulting to using the `np.int32` data type for your matrix. You could use the int64 type instead. However, you'll reach an upper limit here though as well. – Alex Riley Sep 20 '16 at 19:50
  • @ajcr The reason I am curious that a member of the website I am trying to solve the question in, said that the problem is very easy with Python NumPy. This led me to think that this should be achievable. And as a note, `n` goes up to millions. – Rockybilly Sep 20 '16 at 19:52
  • 1
    @Rockybilly: You can certainly do it with NumPy, it's just you'll have to use Python's built in integer type for your matrix if you're calculating large values (this type is slower than the machine-width integers). Just use `(np.matrix("1 1; 1 0", dtype=np.object)**n).item(1)` (i.e. declaring the matrix should use the 'object' type). – Alex Riley Sep 20 '16 at 19:54
  • 1
    @ajcr Could you please add this as an answer where you explain `np.object` ? – Rockybilly Sep 20 '16 at 19:57
  • @ajcr That's the answer, use `numpy.object`. `numpy.uint64` is the largest integer type in numpy and only goes up to 18446744073709551615. – wflynny Sep 20 '16 at 19:57
  • @Rockybilly: I added a quick answer. Hope it helps! – Alex Riley Sep 20 '16 at 20:12

1 Answers1

10

The reason you see negative values appearing is because NumPy has defaulted to using the np.int32 dtype for your matrix.

The maximum positive integer this dtype can represent is 231-1 which is 2147483647. Unfortunately, this is less the 47th Fibonacci number, 2971215073. The resulting overflow is causing the negative number to appear:

>>> np.int32(2971215073)
-1323752223

Using a bigger integer type (like np.int64) would fix this, but only temporarily: you'd still run into problems if you kept on asking for larger and larger Fibonacci numbers.

The only sure fix is to use an unlimited-size integer type, such as Python's int type. To do this, modify your matrix to be of np.object type:

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

The np.object type allows a matrix or array to hold any mix of native Python types. Essentially, instead of holding machine types, the matrix is now behaving like a Python list and simply consists of pointers to integer objects in memory. Python integers will be used in the calculation of the Fibonacci numbers now and overflow is not an issue.

>>> fib_2(300)
222232244629420445529739893461909967206666939096499764990979600

This flexibility comes at the cost of decreased performance: NumPy's speed originates from direct storage of integer/float types which can be manipulated by your hardware.

Alex Riley
  • 169,130
  • 45
  • 262
  • 238