CODEWITHSUNDEEP
pythonfibonacci
Dan
Dan

Reputation: 10171

Python fibonacci doesn't have infinite precision?

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.

Upvotes: 0

Views: 1083

Answers (3)

kxr
kxr

Reputation: 5548

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
>>>

Upvotes: 0

DSM
DSM

Reputation: 353604

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?

Upvotes: 3

Foo Bah
Foo Bah

Reputation: 26281

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.

Upvotes: 4

Related Questions