Benjamin Van Nguyen

A place to hone our problem solving skills and enjoy eldritch art — and hopefully retain our sanity whilst doing so. I post a coding challenge every few days for us to solve together so subscribe at the very bottom of the page to receive email notifications :)

Even Fibonacci Numbers and Memoization

“The most merciful thing in the world, I think, is the inability of the human mind to correlate all its contents. We live on a placid island of ignorance in the midst of black seas of infinity, and it was not meant that we should voyage far. The sciences, each straining in its own direction, have hitherto harmed us little; but some day the piecing together of dissociated knowledge will open up such terrifying vistas of reality, and of our frightful position therein, that we shall either go mad from the revelation or flee from the light into the peace and safety of a new dark age.”

So here's the problem of the day: Even Fibonacci Numbers
 

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.


The prerequisite to understanding this sort of problem is to first be able to construct your own function that gives the nth term of a fibonacci sequence; this can be done either iteratively or recursively. We're going to do it recursively, however, feel free to share how to do it iteratively below!

A typical recursive function that returns the nth term of a fibonacci sequence is as follows:

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

 

Lets quickly talk about the three rules of recursive algorithms and how it relates to the function above:

  1. Recursive algorithms must have a base case.
  2. Recursive algorithms must change state and move towards the base case. 
  3. Recursive algorithms must call itself recursively.

Recursion is a method of problem solving in which we keep breaking up a problem into smaller and smaller subproblems until we arrive so a subproblem small enough so that it can be solved trivially. That "small enough" subproblem is the base case, which is represented by the if and elif statements in the function above. 

Think about it for a minute; if someone asks you, "What's the fifth number in the fib sequence?" — you wouldn't necessarily know right off the top of your head (unless you memorized it, weirdo). You'd have to break the problem into smaller subproblems by changing state and moving towards the base case as per rule number 2, and the state change is facilitated by the return statement which allows the function to call itself recursively. 
 

# fib(5) = fib(4) + fib(3)
# fib(4) = fib(3) + fib(2) 
# fib(3) = fib(2) + fib(1)
# Aa-HAH!
# fib(3) = 2 + 1 = 3
# Therefore
# fib(4) = 3 + 2 = 5
# And 
# fib(5) = 5 + 3 = 8

 

Notice how we kept having to break the problem down until we arrived at the base case — that is, fib(1) and fib(2) — and afterwards the problem just solves itself.

 

Now the next question is: how well does this algorithm perform? Lets test it out.

 

from timeit import Timer

a = [5, 15, 25]

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

for num in a:
    t1 = Timer(f"fib({num})", "from __main__ import fib")
    print(f"{num}th fib: {t1.timeit(number=1000)} milliseconds")

## Results ##
# 5th  fib: 0.0014842259999999982 milliseconds
# 15th fib: 0.14470956299999999 milliseconds
# 25th fib: 17.240876315 milliseconds

 

Now I don't know about you, but I have a life and don't got time to be sitting here waiting 17 milliseconds for the 25th number in the fib sequence. How do we improve this? 


Memoization.

Memoization is fancy way to tell your program to cache or memorize every result it finds along the way that isn't already memorized so that whenever it arrives at a subproblem it had already solved previously, it wouldn't solve it again. Take this for example:

 

                    fib(5)
                   /     \
                  /       \
                 /         \
              fib(4)      fib(3)
              /   \       /    \
         fib(3) fib(2)  fib(2) fib(1)
         /   \
     fib(2)  fib(1)

 

Notice how fib(3) is being solved for twice. Since this is our current case, can you imagine how many repetitive proccesses are going on at higher values of n? That's why our current algorithm doesn't perform so well. Lets fix it using memoization and compare with our previous results. 

def fib(n, cache={1:1, 2:2}):
    if n in cache: # Check to see if n is in the cache's keys.
        return cache[n] # If it is, return its value
    else: # Otherwise
        result = fib(n - 1) + fib(n - 2) # Move towards base case via recursive calls
        cache[n] = result # Memoize/cache the result for future repeated calls
    return result 

 

Now with this refactor, rather than having our algorithm solve the same subproblems it had already solved before, the function will check the dictionary we provided to it called cache, to see if there exists a key-value pair representing a certain number in the fibonacci sequence. If that key-value pair does not exist, we memoize or cache the result for future calls. 

Lets check to see it's performance now:

from timeit import Timer
a = [5, 15, 25]

def fib(n, cache={1:1, 2:2}):
    if n in cache: 
        return cache[n] 
    else: 
        result = fib(n - 1) + fib(n - 2) 
        cache[n] = result 
    return result 
    
for num in a:
    t1 = Timer(f"fib({num})", "from __main__ import fib")
    print(f"{num}th fib: {t1.timeit(number=1000)} milliseconds")

## Result ##

# 5th fib:  0.00031967100000000054 milliseconds
# 15th fib: 0.00030339300000000596 milliseconds
# 25th fib: 0.0003397620000000004 milliseconds

Much better! Now back to the problem at hand.

We are interested in the sum of all even numbers in the fibonacci sequence below 4 million. Well alright — lets apply a bit of forethought:

With all of this in mind take a look below:

def fib(n, cache={1:1, 2:2}):
    if n in cache:
        return cache[n]
    else:
        result = fib(n - 1) + fib(n - 2)
        cache[n] = result
    return result

def even_fib_sum(fib_func=fib): # Supply our new function with our fib function

    nth_fib = 1 # We begin with the first fib number
    result = 0 # This is the value we will increment

    while fib(nth_fib) < 4 * 10**6: # Runs while the fib number is less than 4 million

        if fib(nth_fib) % 2 == 0: # Checks if the fib number is even
            result += fib(nth_fib) # If it is we will increment the result by that number.
        nth_fib += 1 # The next loop will check the next fib number. 
    return result

print(even_fib_sum())

# answer: 4613732

And there you have it. This is, in my opinion, a pretty good solution to the problem; but it can be better. The way I have it set up right now, every successive loop within the while-loop is doing a lot of the same calculations as the ones previously because the cache dictionary's scope is relegated only to within the fib function — which means that all the caching of one iteration does not carry over to the next — so essentially we're caching over and over again with each loop. How do we resolve this? I'll let you guys figure it out.

Hint: It's all about scope.
 

 


Join the discussion:

Log in or Sign up to vote and leave comments.


solidiquis | May 16, 2019, 3:24 a.m.

Questions that user, goodtimes, sent my way that I'll answer here for anyone else who may be confused. 

1. What are the 1s and 2s referring to in the dictionary?

cache={1:1, 2:2} represents the first two fib numbers and their corresponding value. If you take a look at the very first function, we used: if  n == 1, return 1; elif n == 2, return 2. For our refactored function, we use a dictionary instead, checking to see if the fib numbers are already stored in there through the statement, "if n in cache." So if n = 1, the integer 1 exists in cache as a key, so we will then return its associated value, which is also 1, via the call "return cache[n]."

2. How are the fib numbers stored in the dictionary?

In our refactored fib function, pay close attention to what's going on in the else-statement. We declare a variable called "result," and assign it its value via those recursive calls. Once the value is established, we store it in the dictionary by doing cache[n] = result.

3. f"{num}th fib: {t1.timeit(number=1000)} milliseconds"

Don't worry so much about this as it isn't the focus of the problem; however if you're curious let me direct you to something called f-strings (format-strings). The {} inside of the f-string takes in variables and displays its value upon printing. Example:

num = 13
print(f"Friday the {num}th")

# Friday the 13th
4.  What is the purpose of "from__main__import fib"?

I'll give a simplified explanation of this; but I would encourage you to checkout Timeit's documentation for a more in-depth explanation. Essentially, from '__main__ import fib' imports our fib function from the __main__ namespace into the namespace timeit sets up for the timing experiment. Timeit is basically setting up its own little pocket environment to to clean time tests that aren't affected by any stray variables you may have created. If you're unfamiliar with __name__ == '__main__' and how that works, I recommend you go on Youtube and watch Corey Schafer's video about it. 

5. Why can't you just write even_fib_sum(fib) instead of even_fib_sum(fib_func=fib)?

There were many ways to do this, but you CAN do "even_fib_sum(fib)"; just make sure that when you call the function you have to supply it with the fib function as an argument. Simply doing "even_fib_sum(fib)" and then calling it via even_fib_sum() wouldn't work.

6. Why do you set 'result = 0' in the even_fib_sum?

We are trying to determine the sum of all even numbers in the fib sequence up until 4 million; so every time we encounter an even fib number, we will increment result. Example:

First fib: 1 ... result = 0 (Don't increment because odd)
Second fib: 2 ... result = 2 (Second fib is even so add/increment by 2)
Third fib: 3 ... result = 2 (Don't increment because odd)
Fourth fib: 5 ... result = 2
Fifth fib: 8 ... result = 10 (Increment the result by 8 because 8 is even).

7. Does the while loop replace the use of a range? 

Range produces an iterable that is commonly used with for-loops. While-loops are loops that keep running until the condition you provide it becomes False. Example:

hunger_level = 100

while hunger_level > 0:
    hunger_level -= 10

Can you tell me how many times the while-loop will run? :) 

Glad you enjoyed the post! Contact me at callofcthoder@gmail.com if you want more in-depth discussion.

1 | Reply

goodtimes | May 15, 2019, 7:07 p.m.

Just read through your post and was wondering if you could answer a few questions.

In the line:

def fib(n, cache={1:1, 2:2}):

What are the 1s and 2s referring to in the dictionary? How are the fib numbers stored in the dictionary?

This line was especially confusing to me:

for num in a:
    t1 = Timer(f"fib({num})", "from __main__ import fib")
    print(f"{num}th fib: {t1.timeit(number=1000)} milliseconds")

I understand that you imported a timer to track how long your functions are taking for each fib number. What is the 'f' in (f"fin({num})" doing exactly? It seems like you could leave it out.

In your t1 function, what is the purpose of "from__main__import fib" and where are you pulling that from? (It looks like your pulling it from somewhere)

Why can't you just write even_fib_sum(fib) instead of even_fib_sum(fib_func=fib)? You don't seem to use fib_func later in the script so I was wondering what was going on there.

Why do you set 'result = 0' in the even_fib_sum and what do you mean by " this is the value we will incremant?"

Does the while loop replace the use of a range? Is this what is telling the function to increase in value?

I really enjoyed your post. If you could answer any of these that would be so great. Looking forward to the next one!

1 | Reply
solidiquis | May 16, 2019, 3:22 a.m.
Hey goodtimes! Great questions. Since this is going to be quite a lengthy reply I'm going to post a new comment above yours so check that out :)
2 | Reply

solidiquis | May 15, 2019, 1:39 a.m.
if (solution === 'javascript') {
    console.log('Brownie points +1')
};

 

1 | Reply

Subscribe to be notified about new blog entries!

Email