Finding large Fibonacci Number in Python

Question

I'm doing Project Euler at 1000-digit Fibonacci number - Problem 25 which says

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.

Hence the first 12 terms will be:

F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144

The 12th term, F12, is the first term to contain three digits.

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

I approached this by writing a recursive function in Python that finds the n^th Fibonacci number as follows:

def Fibonacci(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        return (Fibonacci(n-1) + Fibonacci(n-2))

However, this function runs very, very slowly. It slows down severely as n approaches 100.

What can I do to make it faster?

Answer 1

Issue

Your issue is you compute fibonacci(i) for one number multiple times.

To understand this, consider computing fibonacci(5). The function would call fibonacci(4) and fibonacci(3) at the end. Now what happens in fibonacci(4)? It would call fibonacci(3) and fibonacci(2). Now you can notice, that the function gets called 2 times for the number 3, which is a serious issue, since that can go VERY deep in the recursion and you can gain a massive overhead because of this.

Solution

Because fibonacci is a pure function, it returns the same value every time it is called with the same parameters. So there's a simple trick you can do to avoid so much time on recalculating what you already found. You can store the result of fibonacci for a specific number in an array, and if it's called again, just return that instead of computing everything again. This trick is called memoization. The Fibonacci sequence is often used as the introductory example for dynamic programming and memoization.

See this nice video explaining the concept of memoization and dynamic programming

Code

This is a simple implementation of memoization for this problem.

cache = {}

def fibonacci(n):
    if n in cache:
        return cache[n]

    if n == 1 or n == 2:
        return 1
    else:
        result = fibonacci(n-1) + fibonacci(n-2)
        cache[n] = result
        return result

Answer 2

Since this is a programming challenge, I'll just sketch out the improvements - you'll learn more by solving it yourself.

You could implement this in C, and doing so may be a little faster, but you'll have the same problem just a bit later on. Your asymptotic complexity scales poorly.

When you calculate Fibonacci(n), you recursively call Fibonacci(n-1) and Fibonacci(n-2). Now, both of these are going to call Fibonacci(n-3), so they are duplicating work.

You need to find some way to remember the earlier computations, to avoid calculating the same values over and over again. You could use the technique of memoization, where you store the results in a suitable container. Or, if you're working linearly through the numbers, you just need to remember the last two terms calculated, and discard anything smaller - that can be done with a couple of variables.

If you want to significantly speed the calculation, you should be aware that there's a closed-form expression for F(n) and for n(F) - but that will probably bypass a lot of what you can learn from this problem.

Answer 3

All the answers are correct in the sense that you compute Fibonacci numbers in a worst possible way. However non of them address the real issue.

The problem statement doesn't ask you to compute the Fibonacci number. It only asks to compute the index of a first Fibonacci number with 1000 digits.

Recall that the number of digits in \$N\$ is \$\lfloor\log_{10}{N}\rfloor + 1\$. Also recall the Binet's formula. Notice that the term including \$(1 - \sqrt{5})^n\$ becomes negligibly small. Conclude that the number of digits in \$F_n\$ is \$1 + \lfloor\log_{10}{\frac{(1 + \sqrt{5})^n}{2^n \sqrt{5}}}\rfloor\$. Simplify and find \$n\$.

Answer 4

The simplest Fibonacci function without memoization and recursion:

def fibonacci(n) :
    a,b = 1,1
    while n > 2 :
        a,b,n = b, b+a, n-1
    return b

But with memoization multiple calls for different inputs will be faster. You can modify this function to find solution in one call:

def fibonacci(digits) :
    a,b,n = 1,1,2
    while len(str(b)) < digits :
        a, b, n = b, b+a, n+1
    return n

Answer 5

The problem with this algorithm is that it runs in exponential run time. C might be faster for a little bit, but you will run into problems with overflows and in the end, I'm not sure the speedup is worth it. There is an algorithm to compute Fibonacci numbers in N time which you can find here