The art of creating efficient algorithms

Audun Nes
Audun Nes
Sep 5, 2018 · 3 min read

How often do we think outside the box to create a creative and efficient algorithm when we develop software? I bet answer is “probably not often enough”.

I use Python for Test Driven Development of Ansible roles, but I don’t get to code as much Python as I would like. It’s one of many tools I use, but not my daily driver. Hence this example is not about how to create good algorithms in general, but rather a reflections on how algorithms affects code performance. So please forgive me for any false assumptions and poor code quality.

While reading a book on Python 3 a few years ago, I came across an interesting anecdote about the German mathematician Carl Friedrich Gauss, who at the age of 8 was given a homework assignment to sum up all the numbers between 1 and 100. To his teacher’s astonishment Carl Friedrich answered 5050 a few seconds later, and it was the teacher had to go home and check if the answer was correct.

Instead of adding every number between 1 and 100, the young Carl Friedrich quickly realized that there were 50 pairs of unequal numbers that would sum up to 100:

99 + 1
98 + 2
And so on, all the way down to 51 + 49

And since he had not included the number 50 yet, the answer was:

(50 pairs * 100) + 50 = 5050

So the youngster had by himself discovered a pretty efficient algorithm for summing up integers. Not bad for an 8 year old! According to Wikipedia this story is contested, but nevertheless it is a very good example of a creative solution for optimizing an algorithm.

So I decided to put this to the test in Python by creating three different methods in a class I called FynnyMath. Two of these functions very slow on purpose:

Slow due to design issue:

The observant reader will see that the major problem in the code block below is that for each iteration I increment the class variable self.num

def slowest(self, num=0):
for i in range(1, self.num):
self.num += i
return int(self.num)

This is documented in the Python Wiki as a poor way to use variables. Reference: https://wiki.python.org/moin/PythonSpeed/PerformanceTips#Local_Variable

Slow due to traditional thinking

The method below looks fine from a traditional approach of summing up number. For each iteration a local variable is update by incrementing the value by 1.

def faster(self, num=0):
num = self.num
for i in range(1, num):
num += i
return int(num)

The Gauss formula

By creating the formula discovered by young Carl Friedrich Gauss, we get the following method:

def fastest(self, num=0):
return int(self.num**2/2.0 + self.num/2.0)

Testing the 3 methods

In order to see a significant benefit of using the Gauss formula, we need to test with a high number, so let’s try summarize all numbers between 1 and 100 millions.

$ python FunnyMath.py 
Slowest approach took 10.85 seconds to get the result: 5000000050000000
Faster approach took 4.44 seconds to get the result: 5000000050000000
Fastest approach took 0.0 seconds to get the result: 5000000050000000

So this is just one example how it matters to thing outside the box when creating algorithms. The full source code can be seen at https://github.com/avnes/perftest/

Audun Nes

Written by

DevOps Engineer from Copenhagen, Denmark. GitHub: https://github.com/avnes

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade