Even Fibonacci numbers

Today, I am going to solve Project Euler’s 2nd problem Even Fibonacci numbers.

Day 002

Problem statement:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Solution

The easiest way to solve this problem is get fibonacci series and check if the value is even then sum it. The execution actually took a while to complete.

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

sum = 0
counter = 0

while fibonacci(counter) <= 4000000:
    fib = fibonacci(counter)
    if fib % 2 == 0:
        sum += fib
    counter += 1

print(sum)

But we can improve this code a lot by caching the recursive function call result and calculate only if the number doesn’t exists in the result cache.


result_cache = {}

def fibonacci(n):
    result = result_cache.get(n)

    if result:
        # if result is present in cache return result
        return result
    else:
        # if result is not present in cache calculate
        if n <= 1:
            result = 1
        else:
            result = fibonacci(n - 1) + fibonacci(n - 2)

    # set result on cache
    result_cache[n] = result
    return result_cache[n]


sum = 0
counter = 0

while fibonacci(counter) <= 4000000:
    fib = fibonacci(counter)
    if fib % 2 == 0:
        sum += fib
    counter += 1

print(sum)

Today’s thoughts

Caching the results actually made the program run faster. Performance should be kept in mind while writing code. Simple steps to improve the code is first make it work, make it right, make it fast.