OverflowError 'Numerical result out of range' when generating fibonacci numbers [duplicate]

Question

Possible Duplicate:
Handling very large numbers in Python

I have a python function to generate fibonacci numbers:

def fib(n):                                                                                                            
        return ((1+math.sqrt(5))**n - (1-math.sqrt(5))**n)/(2**n*math.sqrt(5))

I can feed the fib function numbers up to 700, where it starts to

OverflowError: (34, 'Numerical result out of range')

Do I need to use a special type like long to get around this?

Answer 1

The problem is that you're using doubles to calculate the value and the doubles are overflowing. Doubles give exact solutions only to about the 85th Fibonacci number.

If you want a fast and accurate calculation you're better off using an algorithm based on a better recurrence relationship, and using python bignum integers.

In particular you can use:

 fib(2*n) = fib(n)^2 + fib(n-1)^2
 fib(2*n-1) = fib(n)*(2*fib(n-1)+fib(n))

Or the equivalent matrix exponentiation formula (excuse the ugly formatting)

 [ F_n     F_{n-1} ]      [ 1   1 ] ^N 
 [                 ]  =   [       ]
 [ F_{n-1} F_{n-2} ]      [ 1   0 ]

Both of these result in algorithms that require O(log(N)) calculations rather than O(N).

Here's a complete solution in pseudo-code

---

If you do want to perform your calculations using doubles and the explicit formulae, then the formulae can be tweaked to give something faster that doesn't overflow until about the 1500th fibonacci number, and remains the same accuracy as your version. IIRC it is:

def fib(n):                                                                                                            
    return round( ((1+math.sqrt(5))/2)**n / math.sqrt(5) )

Answer 2

It's easy to isolate the error

>>> (1+math.sqrt(5))**700
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
OverflowError: (34, 'Numerical result out of range')

This method won't work well as floating point numbers don't have enough precision

for example, here

>>> (1+math.sqrt(5))**600
1.024664165563927e+306

you are working with only the first 15 or so digits. The remaining 291 will be treated as zeros when you do any arithmetic

See wikipedia for more information about accuracy problems with floating point numbers