Python fibonacci doesn't have infinite precision?

Question

I'm try to write a fast fibonacci algorithm in python that can be used for extremely large values, but I keep getting negative values, so I'm assuming its not properly using longs?

fibonacci_matrix = numpy.matrix([[1,1],[1,0]])
def fib(n):
  return (fibonacci_matrix**(n-1)) [0,0]

fibonacci_matrix2 = numpy.matrix([[1L,1L],[1L,0L]])
def fib2(n):
  return (fibonacci_matrix2**(n-1)) [0,0]

def fib3(n):
  if n in [1,2]:
    return 1L
  else:
    return long(long(fib2(n-1))+long(fib2(n-2)))

print fib(47)
print fib2(93)
print fib3(95)

Which gives me output:

-1323752223
-6246583658587674878
-4953053512429003327

instead of positive values like all fibonacci numbers should be.

Can someone help troubleshoot this? Or better yet help me write an improved, efficient and infinetly accurate fibonnaci sequence code? Most of my googling yields terrible basic slow recursive fibonnacci algorithms.

score 4 · Answer 1 · answered Oct 09 '11 at 23:21

4

You are seeing overflow. Assuming a long is 32-bit, the range of values that it can store is -2^31 .. 2^31 - 1 and the 47th fibonacci number is 2971215073.

To do this accurately you need larger integers. Python supports them natively, but I dont think numpy supports them ...

As a pure python example:

def fib4(n):
    x=[1,1]
    for i in xrange(n-2):
        x.append(x[-1]+x[-2])
    return x[-1]

This forces python to use larger integer values in calculation.

answered Oct 09 '11 at 23:21

Foo Bah

24,723
5
52
79

I don't know why this works better than by fib3, but it apparently works much better, thank you. Do you know what I did wrong? I tried adding a bunch of long()'s to it, but it didn't help. Is there anyway I could still do an efficient method? The only fib methods I know of are basic recursion like this one, the sqrt(5) method (which would be hard to manage its accuracy) and the matrix form, which sounds like I would have to stay away from numpy to accomplish it right. – Dan Oct 10 '11 at 00:12
1

@Dan this is simply translating the recursive form to an iterative form. It is inefficient inasfar as you cache all of the values (but involves less operations than the matrix form). The accuracy of the binet formula is shaky. – Foo Bah Oct 10 '11 at 00:17

score 4 · Accepted Answer · answered Oct 09 '11 at 23:43

You can make numpy use Python arbitrary-precision integers by setting the dtype to object:

>>> fibonacci_matrix = numpy.matrix([[1,1],[1,0]], dtype=object)
>>> def fib(n): return (fibonacci_matrix**(n-1)) [0,0]
>>> 
>>> fib(100)
    354224848179261915075L

but I don't know how much that will help. Usually if you want a really fast implementation of some recursive function like this, you use the various identities to do reductions. For example, using the identity F(2*n) = F(n+1)^2-F(n-1)^2 allows a nice logarithmic evaluation. [Actually, Wikipedia lists a generalization of this which is even better.]

Is there some reason you really need speed?

score 0 · Answer 3 · answered Aug 04 '16 at 12:29

Regarding "efficient and infinetly accurate fibonnaci sequence code" in python: Simple recursion series like this can be computed fast and easy by exploiting the out argument of numpy ufuncs. Precision by appropriate data type.

Albeit in the case of fibonacci numbers with standard seeds - there are not much within reasonable numerical scope and you could exploit advanced mathematical properties - this might be of general interest:

>>> a = np.zeros(102, object)
>>> a[1] = 1; a[0] = 0
>>> np.add(a[:-2], a[1:-1], out=a[2:])
array([1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597,
       2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418,
       317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465,
       14930352, 24157817, 39088169, 63245986, 102334155, 165580141,
       ....
       7540113804746346429, 12200160415121876738, 19740274219868223167,
       31940434634990099905, 51680708854858323072, 83621143489848422977,
       135301852344706746049, 218922995834555169026, 354224848179261915075,
       573147844013817084101], dtype=object)
>>> a[100]
354224848179261915075L
>>> a[51]**2 - a[49]**2
354224848179261915075L
>>>

Python fibonacci doesn't have infinite precision?

3 Answers3