Python prevent overflow errors while handling large floating point numbers and integers

Question

I am working on a python program to calculate numbers in the Fibonacci sequence. Here is my code:

import math
def F(n):
    return ((1+math.sqrt(5))**n-(1-math.sqrt(5))**n)/(2**n*math.sqrt(5))
def fib(n):
    for i in range(n):
        print F(i)

My code uses this formula for finding the Nth number in the Fibonacci sequence:

This can calculate many of the the numbers in the Fibonacci sequence but I do get overflow errors.

How can I improve this code and prevent overflow errors?

Note: I am using python 2.7.

Answer 1

Python's integers are arbitrary precision so if you calculate the Fibonacci sequence using an interative algorithm, you can compute exact results.

>>> def fib(n):
...   a = 0
...   b = 1
...   while n > 0:
...     a, b = b, a + b
...     n = n - 1
...   return a
... 
>>> fib(100)
354224848179261915075L

There are several multiple precision floating-point libraries available for Python. The decimal module is included with Python and was originally intended for financial calculations. It does support sqrt() so you can do the following:

>>> import decimal
>>> decimal.setcontext(decimal.Context(prec=40))
>>> a=decimal.Decimal(5).sqrt()
>>> a
Decimal('2.236067977499789696409173668731276235441')
>>> ((1+a)**100 - (1-a)**100)/(a*(2**100))
Decimal('354224848179261915075.0000000000000000041')

Other libraries are mpmath and gmpy2.

>>> import gmpy2
>>> gmpy2.set_context(gmpy2.context(precision=150))
>>> a=gmpy2.sqrt(5)
>>> a
mpfr('2.2360679774997896964091736687312762354406183598',150)
>>> ((1+a)**100 - (1-a)**100)/(a*(2**100))
mpfr('354224848179261915075.00000000000000000000000248',150)
>>> gmpy2.fib(100)
mpz(354224848179261915075L)

gmpy2 can also computer Fibonacci numbers directly (as shown above).

Disclaimer: I maintain gmpy2.

Answer 2

I don't know if this is acceptable to you, but you could just use integer arithmetic as calculate the fib number using the recurrence relation (e.g., F3 = F2 + F1).

Since Python 2.5?, you can do arbitrary precision integer arithmetic -- pretty much eliminate overflow problems -- If you try to calculate F(10000) it will doubtless get very slow.

Also, check out the decimal module -- IIRC correctly, you can use in with Python 2.7, you can specify the precision of the decimal arithmetic -- This would allow you to continue using same algorithm -- except for using the decimal type.

ADDED

You can easily overlook that the decimal class includes a square root method. You would need to use this method instead of math.sqrt() since you will need to retain the full precision of the decimal class.

Also sqrt(5) is a relatively expensive operation. Only calculate it one time

Answer 3

Your statement of How can I improve this code... is kind of vague, so I will take it to mean shortening your code:

import math
def fib(j):
    for i in [int(((1+math.sqrt(5))**n-(1-math.sqrt(5))**n)/(2**n*math.sqrt(5))) for n in range(j)]: print i

You can combine both of your functions to make just one function, and using list comprehension, you can make that function run in one line.

You cannot prevent overflow errors if you are working with very large numbers, instead, try catching them and then breaking:

import math
def fib(j):
        try:
                for i in [int(((1+math.sqrt(5))**n-(1-math.sqrt(5))**n)/(2**n*math.sqrt(5))) for n in range(j)]: print i
        except Exception as e:
                print 'There was an error, your number was too large!'

The second one will first loop over everything and make sure there is no error, and if there isn't, it will proceed to print it.