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