Project Euler Solution 2: Even Fibonacci numbers

Here we have the second entry in the Project Euler series, this time about Problem 2: Even Fibonacci numbers where we shall sum up the even Fibonacci numbers up to a certain threshold.

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.

A very naive version would be to implement the Fibonacci numbers according to their mathematical definition and use a recursive approach. This implementation is so bad that it is one of the infamous negative examples. Still I can show how bad it is. We have a funtion for the Fibonacci numbers and then iterate over the numbers, check whether they are even, and then accumulate them.

def fibonacci_recursive(n) -> int:
    if n == 0:
        return 1
    elif n == 1:
        return 2
    else:
        return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)


def solution_naive() -> int:
    fib_sum = 0
    for i in itertools.count():
        fib_i = fibonacci_recursive(i)
        if fib_i % 2 == 0:
            fib_sum += fib_i
        if fib_i > 4_000_000:
            break
    return fib_sum

This does yield the answer of 4,613,732, but it takes 946 ms to compute. The questions are made up such that they can be computed quite quickly with modest computers. Their limit is about one minute, so this is okay. But I know that this problem can be solved faster than with the above solution.

We can do better by not having this exponential complexity in the Fibonacci numbers and just remembering the previous two numbers. In Python we can use a generator to encapsulate this state in a coroutine. And then we can loop over the Fibonacci numbers as before.

def fibonacci_generator() -> Iterator[int]:
    yield 1
    yield 2
    previous = 1
    current = 2
    while True:
        previous, current = current, current + previous
        yield current


def solution_generator() -> int:
    fib_sum = 0
    for fib_i in fibonacci_generator():
        if fib_i % 2 == 0:
            fib_sum += fib_i
        if fib_i > 4_000_000:
            break
    return fib_sum

This takes 3 µs to solve the problem and yield the answer of 4613732. So this is a factor 300,000 faster than the previous version! No surprise there, because it is of complexity O(N) where N is the ceiling of 4,000,000. The naive version is O(2^N), which is brutal.

Since we need all the Fibonacci numbers, one can generate them in this iterative fashion with O(N) and then have amortized cost of O(1) per number. That is fine. But if we needed a random access to the numbers, it would still cost us O(N) to get to any of the numbers (unless we cache them, introducing O(N) memory demand). There is a way to diagonalize the Fibonacci sequence and have an equation to compute the N-th number with O(1) cost, no matter how large N is. That is pretty cool!