Project Euler #25: Keep getting Overflow error (result to large) - is it to do with calculating fibonacci number?

I'm working on solving the Project Euler problem 25:

What is the first term in the Fibonacci sequence to contain 1000 digits?

My piece of code works for smaller digits, but when I try a 1000 digits, i get the error:

OverflowError: (34, 'Result too large')

I'm thinking it may be on how I compute the fibonacci numbers, but i've tried several different methods, yet i get the same error.

Here's my code:

'''
 What is the first term in the Fibonacci sequence to contain 1000 digits
'''

def fibonacci(n):
    phi = (1 + pow(5, 0.5))/2           #Golden Ratio
    return int((pow(phi, n) - pow(-phi, -n))/pow(5, 0.5))   #Formula: http://bit.ly/qDumIg


n = 0
while len(str(fibonacci(n))) < 1000:
    n += 1
print n

Do you know 开发者_如何转开发what may the cause of this problem and how i could alter my code avoid this problem?

Thanks in advance.

The problem here is that only integers in Python have unlimited length, floating point values are still calculated using normal IEEE types which has a maximum precision.

As such, since you're using an approximation, using floating point calculations, you will get that problem eventually.

Instead, try calculating the Fibonacci sequence the normal way, one number (of the sequence) at a time, until you get to 1000 digits.

ie. calculate 1, 1, 2, 3, 5, 8, 13, 21, 34, etc.

By "normal way" I mean this:

         /  1                        , n < 3
Fib(n) = |
         \  Fib(n-2) + Fib(n-1)      , n >= 3

Note that the "obvious" approach given the above formulas is wrong for this particular problem, so I'll post the code for the wrong approach just to make sure you don't waste time on that:

def fib(n):
    if n <= 3:
        return 1
    else:
        return fib(n-2) + fib(n-1)

n = 1
while True:
    f = fib(n)
    if len(str(f)) >= 1000:
        print("#%d: %d" % (n, f))
        exit()
    n += 1

On my machine, the above code starts going really slow at around the 30th fibonacci number, which is still only 6 digits long.

I modified the above recursive approach to output the number of calls to the fib function for each number, and here are some values:

#1: 1
#10: 67
#20: 8361
#30: 1028457
#40: 126491971

I can reveal that the first Fibonacci number with 1000 digits or more is the 4782th number in the sequence (unless I miscalculated), and so the number of calls to the fib function in a recursive approach will be this number:

1322674645678488041058897524122997677251644370815418243017081997189365809170617080397240798694660940801306561333081985620826547131665853835988797427277436460008943552826302292637818371178869541946923675172160637882073812751617637975578859252434733232523159781720738111111789465039097802080315208597093485915332193691618926042255999185137115272769380924184682248184802491822233335279409301171526953109189313629293841597087510083986945111011402314286581478579689377521790151499066261906574161869200410684653808796432685809284286820053164879192557959922333112075826828349513158137604336674826721837135875890203904247933489561158950800113876836884059588285713810502973052057892127879455668391150708346800909439629659013173202984026200937561704281672042219641720514989818775239313026728787980474579564685426847905299010548673623281580547481750413205269166454195584292461766536845931986460985315260676689935535552432994592033224633385680958613360375475217820675316245314150525244440638913595353267694721961

And that is just for the 4782th number. The actual value is the sum of all those values for all the fibonacci numbers from 1 up to 4782. There is no way this will ever complete.

In fact, if we would give the code 1 year of running time (simplified as 365 days), and assuming that the machine could make 10.000.000.000 calls every second, the algorithm would get as far as to the 83rd number, which is still only 18 digits long.

Actually, althought the advice given above to avoid floating-point numbers is generally good advice for Project Euler problems, in this case it is incorrect. Fibonacci numbers can be computed by the formula F_n = phi^n / sqrt(5), so that the first fibonacci number greater than a thousand digits can be computed as 10^999 < phi^n / sqrt(5). Taking the logarithm to base ten of both sides -- recall that sqrt(5) is the same as 5^(1/2) -- gives 999 < n log_10(phi) - 1/2 log_10(5), and solving for n gives (999 + 1/2 log_10(5)) / log_10(phi) < n. The left-hand side of that equation evaluates to 4781.85927, so the smallest n that gives a thousand digits is 4782.

You can use the sliding window trick to compute the terms of the Fibonacci sequence iteratively, rather than using the closed form (or doing it recursively as it's normally defined).

The Python version for finding fib(n) is as follows:

def fib(n):
    a = 1
    b = 1
    for i in range(2, n):
        b = a + b
        a = b - a
    return b

This works when F(1) is defined as 1, as it is in Project Euler 25.

I won't give the exact solution to the problem here, but the code above can be reworked so it keeps track of n until a sentry value (10**999) is reached.

An iterative solution such as this one has no trouble executing. I get the answer in less than a second.

def fibonacci():
    current = 0 
    previous = 1
    while True:
        temp = current
        current = current + previous
        previous = temp
        yield current


def main():
for index, element in enumerate(fibonacci()):
    if len(str(element)) >= 1000:
        answer = index + 1 #starts from 0
        break
print(answer)

import math as m
import time
start = time.time()
fib0 = 0
fib1 = 1
n = 0
k = 0
count = 1    
while k<1000 :
        n = fib0 + fib1
        k = int(m.log10(n))+1
        fib0 = fib1
        fib1 = n
        count += 1
print n 
print count
print time.time()-start

takes 0.005388 s on my pc. did nothing fancy just followed simple code. Iteration will always be better. Recursion was taking to long for me as well. Also used a math function for calculating the number of digits in a number instead of taking the number in a list and iterating through it. Saves a lot of time

Here is my very simple solution

list = [1,1,2]
for i in range(2,5000):
    if len(str(list[i]+list[i-1])) == 1000:
        print (i + 2)
        break
    else:
        list.append(list[i]+list[i-1])

This is sort of a "rogue" way of doing it, but if you change the 1000 to any number except one, it gets it right.

You can use the datatype Decimal. This is a little bit slower but you will be able to have arbitrary precision.

So your code:

'''
What is the first term in the Fibonacci sequence to contain 1000 digits
'''

from Decimal import *

def fibonacci(n):
    phi = (Decimal(1) + pow(Decimal(5), Decimal(0.5))) / 2           #Golden Ratio
    return int((pow(phi, Decimal(n))) - pow(-phi, Decimal(-n)))/pow(Decimal(5), Decimal(0.5)))


n = 0
while len(str(fibonacci(n))) < 1000:
    n += 1
print n