1000-Digit Number in Python

Question

I was solving project Euler wherein I came across a question which asked me the index of first 1000 digit fibonacci num.

First I used this code but was taking too much of time.

def fibonacci(num):
    if (num==0):
        return 0;
    if(num==1):
        return 1;
    return fibonacci(num-1) + fibonacci(num-2);


def numOfDigits(num):
    numOfDigits = 0;
    while (num>0):
        num = num/10;
        numOfDigits += 1;
    return numOfDigits;

def main():
    n=0;
    while(n>=0):
        fib = fibonacci(n);
        num = numOfDigits(fibonacci(n));
        print n,"\t",fib;
        if(num>=1000):
            break;
        n+=1;
    print "answer:",n;
main();

Then I googled a little and found the binnet's formula which made it highly faster.

import math as mt;

def fibonacci(num):
    phi = (mt.sqrt(5)+1.00)/2.00;
    return ((phi**num)-((-phi)**(-num)))/mt.sqrt(5);

def numOfDigits(num):
    numOfDigits = 0;
    while (num>0):
        num = num/10;
        numOfDigits += 1;
    return numOfDigits;

def main():
    n=0;
    while(n>=0):
        fib = fibonacci(n);
        num = numOfDigits(fibonacci(n));
        print n,"\t",fib;
        if(num>=1000):
            break;
        n+=1;
    print "answer:",n;
main();

But then the problem occurred here:

1471    1.17851144788e+307
1472    1.9068715788e+307
1473    3.08538302668e+307
1474    4.99225460548e+307
Traceback (most recent call last):
  File "src/ThousandDigitFibonacciNum.py", line 29, in <module>
    main();
  File "src/ThousandDigitFibonacciNum.py", line 22, in main
    fib = fibonacci(n);
  File "src/ThousandDigitFibonacciNum.py", line 10, in fibonacci
    return ((phi**num)-((-phi)**(-num)))/mt.sqrt(5);
OverflowError: (34, 'Result too large')

The first doubt is that is the result too large to return or calculate? And then what is the solution to this?

Answer 1

For each n, you're recalculating all of the fibonacci numbers F(1)...F(n-1) in order to calculate F(n). Instead, you can calculate each fibonacci number only once, checking for each if it has the appropriate number of digits:

def fibo():
    a = 0
    b = 1
    while True:
        yield a
        a, b = b, a+b

for index, number in enumerate(fibo()):
    if len(str(number)) == 1000:
        print(index)
        break