Recently I was faced with a challenge from Project Euler and asked how I would best optimize the solution I wrote. Thinking for a little bit, I made a few changes, but none were as efficient as memoization.
Memoization is the idea of storing data in memory so it is available to be referenced again at a later time, instead of running logic that you have already ran with the same inputs. I’ll show you how we can use memoization and a little bit of basic math to optimize a different problem from Project Euler.
Project Euler Problem #21: Amicable Numbers
1 2 3 4 5 6 7 8 

You can find my first solution here. Obviously, the most expensive operations in an program are those which iterate or recurse. In this case, we have one different loop that looks particularly expensive:
1 2 3 4 5 6 7 

Here, we attempt to divide each number by each number smaller than it. If we are calling this loop on elements, then this will loop times for every , for a time complexity of .
As the problem states, we need to compare the sum of the proper divisors to the proper divisors of the sum itself. Therefore, we call the above method twice in this method:
1 2 3 4 5 6 7 8 9 

So, we wrote this program. Let’s see how long it takes:
1


Ok, let’s try to do better. First of all, let’s think of a math way to fix that find_sum_of_divisors method. No ruby magic here. Since there are no integers less than 2 that divide into any number to come up with a proper divisor, all the numbers given an in $n\ge a\gt n/2$ do not need to be evaluated as those will always be $\gt2$. So instead of num.times in ruby, we can change it to:
1 2 3 4 5 6 7 

Now let’s try running the program again:
1


We’ve, predictably, sliced our running time in half. Great! But we can do better. Remember memoization? Let’s do that.
When we run this problem, it is very possible that we will be running find_sum_of_divisors on the same number multiple times. Because this is a posibility, we can try storing the result of each method call in a hash and referencing it if we need it again, instead of calling the same method again.
To do this, let’s initialize an empty hash each time we instantiate a new Amicable object.
1 2 3 4 

Finally, every time we go to call the find_sum_of_divisors method, we should check to see if we already have for a given number. If we do, we can just use that data and not call the method, saving valuable time:
1 2 3 4 5 6 7 8 9 

Great, now instead of calling a method, we can refernce data in a hash. Let’s see how much faster we made it:
1


Just under two seconds, awesome! I’m sure there’s even more optimizations possible. Submit a pull request to my code if you want to try. You can check out my Github repo for the problem here.