Non Brute Force Solution to Project Euler 25

Question

Project Euler problem 25:

The Fibonacci sequence is defined by the recurrence relation:

F_n = F_n−1 + F_n−2, where F_{1 = 1} and F₂ = 1. Hence the first 12 terms will be F₁ = 1, F₂ = 1, F₃ = 2, F₄ = 3, F₅ = 5, F₆ = 8, F₇ = 13, F₈ = 21, F₉ = 34, F₁₀ = 55, F₁₁ = 89, F₁₂ = 144

The 12th term, F₁₂, is the first term to contain three digits.

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

I made a brute force solution in Python, but it takes absolutely forever to calculate the actual solution. Can anyone suggest a non brute force solution?

def Fibonacci(NthTerm):
    if NthTerm == 1 or NthTerm == 2:
        return 1 # Challenge defines 1st and 2nd term as == 1
    else:  # recursive definition of Fib term
        return Fibonacci(NthTerm-1) + Fibonacci(NthTerm-2)

FirstTerm = 0 # For scope to include Term in scope of print on line 13
for Term in range(1, 1000): # Arbitrary range
    FibValue = str(Fibonacci(Term)) # Convert integer to string for len()
    if len(FibValue) == 1000:
        FirstTerm = Term
        break # Stop there
    else:
        continue # Go to next number
print "The first term in the\nFibonacci sequence to\ncontain 1000 digits\nis the", FirstTerm, "term."

Answer 1

You can write a fibonacci function that runs in linear time and with constant memory footprint, you don't need a list to keep them. Here's a recursive version (however, if n is big enough, it will just stackoverflow)

def fib(a, b, n):
    if n == 1:
        return a
    else: 
        return fib(a+b, a, n-1)


print fib(1, 0, 10) # prints 55

This function calls itself only once (resulting in around N calls for a parameter N), in contrast with your solution which calls itself twice (around 2^N calls for a parameter N).

Here's a version that won't ever stackoverflow and uses a loop instead of recursion:

def fib(n):
    a = 1
    b = 0
    while n > 1:
        a, b = a+b, a
        n = n - 1
    return a

print fib(100000)

And that's fast enough:

$ time python fibo.py 
3364476487643178326662161200510754331030214846068006390656476...

real    0m0.869s

But calling fib until you get a result big enough isn't perfect: the first numbers of the serie are calculated multiple times. You can calculate the next fibonacci number and check its size in the same loop:

a = 1
b = 0
n = 1
while len(str(a)) != 1000:
    a, b = a+b, a
    n = n + 1
print "%d has 1000 digits, n = %d" % (a, n)

Answer 2

Why hasn't anybody used generators for this? This is a brute force solution, but it is very quick:

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

This gives a generator that computes the Fibonacci sequence. For example

f = fibo()
[next(f) for i in range(10)]

produces

[1,1,2,3,5,8,13,21,34,55]

Using this, we can solve the problem like so:

f = enumerate(fibo())
x = 0
while len(str(x)) < 1000:
    i,x = next(f)

print("The %d-th term has %d digits"%(i+1,len(str(x))))

This produces the output

The 4782-th term has 1000 digits

The generator computes the sequence and produces terms 1 by 1 and this solution runs nearly instantly.

Answer 3

Two things can be optimized a lot with one little change in your code. These two things are:

• You compute each fibonacci number using two other fibonacci numbers, resulting in an exponential complexity (which explodes even if you'd only compute a single but high fibonacci number).

• You don't remember any previous computed fibonacci number to compute the next in your loop.

Simply remember all computed fibonacci numbers as a private implementation detail in Fibonacci and you get rid of both performance problems. You can do this by using a simple dynamic array to which you add the result if it wasn't cached before.

Pseudo-code (I don't speak Python but this can be easily implemented):

def Fibonacci(NthTerm):
    if (cache contains NthTerm)
        return cache[NthTerm]
    else
        FibValue = Fibonacci(NthTerm-1) + Fibonacci(NthTerm-2)
        cache[NthTerm] = FibValue
        return FibValue

This will result in very restricted recurion, since you compute the N-th fibonacci number only if you already know (and cached) the (N-1)-th number.

This optimization works even if you need any fibonacci number (for future problems), but in this particular case we know that we only need to remember the last two numbers since we're never going to ask for old numbers again. So you don't need a whole list of numbers but only two, which you "cycle through" for each step in your main loop. Something like

f1, f2 = f2, f1 + f2

within the loop and an initialization like

f1, f2 = 1, 1

will essentially replace your function Fibonacci and its performance problems, but it restricts you to this limited use case.

Answer 4

You can try to use newton's approximation method on binet's formula. The idea is to find a tangent line on the graph and use the x-intercept of that line to approximate the value of the zero of the graph.