CODEWITHSUNDEEP
pythonfibonacci
berkju
berkju

Reputation: 23

Inaccurate Large Fibonacci Numbers in Python

I am currently implementing this simple code trying to find the n-th element of the Fibonacci sequence using Python 2.7:

import numpy as np

def fib(n):
        F = np.empty(n+2) 
        F[1] = 1
        F[0] = 0
        for i in range(2,n+1):
            F[i]=F[i-1]+F[i-2]
        return int(F[n])

This works fine for F < 79, but after that I get wrong numbers. For example, according to wolfram alpha F79 should be equal to 14472334024676221, but fib(100) gives me 14472334024676220. I think this could be caused by the way python deals with integers, but I have no idea what exactly the problem is. Any help is greatly appreciated!

Upvotes: 2

Views: 517

Answers (4)

Copperfield
Copperfield

Reputation: 8520

Unless you want to generate a list with all the fibonacci numbers until Fn, there is no need to use a list, numpy or anything else like that, a simple loop and 2 variables will be enough as you only really need to know the 2 previous values

def fib(n):
   Fk, Fk1 = 0, 1
   for _ in range(n):
      Fk, Fk1 = Fk1, Fk+Fk1
   return Fk

of course, there is better ways to do it using the mathematical properties of the Fibonacci numbers, with those we know that there is a matrix that give us the right result

import numpy

def fib_matrix(n):
    mat = numpy.matrix( [[1,1],[1,0]], dtype=object) ** n
    return mat[0,1]

to which I assume they have an optimized matrix exponentiation making it more efficient that the previous method.

Using the properties of the underlying Lucas sequence is possible to do it without the matriz, and equally as efficient as exponentiation by squaring and with the same number of variables as the other, but that is a little harder to understand at first glance unlike the first example because alongside the second example it require more mathematical.

The close form, the one with the golden ratio, will give you the result even faster, but that have the risk of being inaccurate because the use of floating point arithmetic.

Upvotes: 1

juanpa.arrivillaga
juanpa.arrivillaga

Reputation: 96350

Python will deal with integers perfectly fine here. Indeed, that is the beauty of python. numpy, on the other hand, introduces ugliness and just happens to be completely unnecessary, and will likely slow you down. Your implementation will also require much more space. Python allows you to write beautiful, readable code. Here is Raymond Hettinger's canonical implementation of iterative fibonacci in Python:

def fib(n):
    x, y = 0, 1
    for _ in range(n):
        x, y = y, x + y
    return x

That is O(n) time and constant space. It is beautiful, readable, and succinct. It will also give you the correct integer as long as you have memory to store the number on your machine. Learn to use numpy when it is the appropriate tool, and as importantly, learn to not use it when it is inappropriate.

Upvotes: 2

Thomas Baruchel
Thomas Baruchel

Reputation: 7517

As an additional word to the previous answer by hiro protagonist, note that if using Numpy is a requirement, you can solve very easely your issue by replacing:

F = np.empty(n+2)

with

F = np.empty(n+2, dtype=object)

but it will not do anything more than transferring back the computation to pure Python.

Upvotes: 0

hiro protagonist
hiro protagonist

Reputation: 46921

the default data type for a numpy array is depending on architecture a 64 (or 32) bit int.

pure python would let you have arbitrarily long integers; numpy does not.

so it's more the way numpy deals with integers; pure python would do just fine.

Upvotes: 11

Related Questions