Optimizing code with algebra

Photo by Roman Mager on Unsplash

During a semester in college I took a subject called "Discrete Mathematics". The lecturer decided to split the class in groups. Each group consisted of 2 or 3 students. They were meant to do expositions about a particular subject assigned by the lecturer.

In the group I was on (we were only two, actually), we were assigned with the subject of recurrency relations. According to Wikipedia, this is:

an equation that recursively defines a sequence or multidimensional array of values, once one or more initial terms are given: each further term of the sequence or array is defined as a function of the preceding terms.

In other words, a recursive function ;)

A perfect situation to explain this concept with code :D

Hanoi Towers

Do you remember this toy?

The famous Hanoi Towers. The game consists of moving every disk from the first pole to the last one (from left to right or viceversa) in the least amount of steps possible. The rules are that a bigger disk cannot be over a smaller one and you can move only one disk at the time. Something like this:

This problem has an algorithm that solves it, it goes like this:

Where n is the amount of disks in the problem.

Let's code that

Let's use Python to write that algorithm. It's something like this:

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

So if we have 4 disks...

>>> hanoi(4)
15

Good. It works. Let's give it a few tries

>>> hanoi(5)
31
>>> hanoi(10)
1023
>>> hanoi(40)
1099511627775

Looks pretty good. Now I know how many moves it will take me if I'm using 40 disks (btw, this is gonna take you 10460 years, never try this at home). But what if I have 7000?

>>> hanoi(7000)
Traceback (most recent call last):which
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in hanoi
  File "<stdin>", line 3, in hanoi
  File "<stdin>", line 3, in hanoi
  [Previous line repeated 994 more times]
  File "<stdin>", line 2, in hanoi
RecursionError: maximum recursion depth exceeded in comparison

Oh... It seems this is not performant enough. Of course you could "solve" this just increasing the maximum recursion depth in Python (with sys.setrecursionlimit(n)), but it's a much better idea to optimize this.

Optimizing

There are several ways to solve recurrence relations, one of them is iteration. It consists of solving the operation step by step and deducting the non-recursive equation from the process. First we try to solve a given value:

Then, from the last line, we can deduce an equivalent equation:

If you notice, t(4) = 8 + 7 is the same as t(4) = 2^(4-1) + (2^(4-1) - 1), that's why it's our initial statement. But now we have solved the recurrence relation, let's use that in our code.

def better_hanoi(n):
    return 2**n - 1

And then...

Now we know how many steps will take to solve it with 7000 disks (probably the lifetime of the universe, several times).

Conclusion

We have optimized a small algorithm with concepts of discrete mathematics, this is just to give a little insight on how we can benefit of such simple concepts to build better programs.