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.