It’s easy when solving a problem to become irritated and just push out a clumsy solution. In doing this we completely forget about the art of programming! While every now and then, there are problems that can just have a solution pushed out, generally its better to spend some time in how you solve the problem as well as how you implement the solution.

This is the first blog post in a series of blog posts that will cover problem solving as an art. This first post is going to cover the basics of problem solving as well as some of the different steps involved. Later on we will cover the individual steps in greater detail.

Step 1 Defining the problem

The first thing that must be done is defining the problem. We’ll start off with a simple problem that I enjoy as an example problem: How do you decide if a number is even or odd? Of course most programmers know how to solve this problem, which makes it a prime first example.

Our original way of stating the problem seems to be fine (that is: How do you decide if a number is even or odd?) Although this seems like a fine way to put the question, it is not specific enough. We don’t mention any constraints, as well as we don’t mention any specifics. So, lets redefine our question mentioning the language we want to solve this problem in, and a engineering constraint.

How do you decide if a number is even or odd efficiently in C? While this looks quite similar, it is much more clear. We state our final goal (finding out if a number is even or odd), our secondary focus (efficiency), and what language we will be solving this problem in (C).

Step 2 Defining possible solutions

Now that we have a problem, we must create a solution to this problem. Depending on the type of problem, there are several ways to solve it. This problem happens to be one that humans can accomplish. We have the ability to tell if a number is even or odd. This gives us a head start. We should ask our selves: How do I tell if a number is even or odd?

There are several ways we determine if a number is even or odd. If the number ends in 0, 2, 4, 6, or 8 the number is even, if not the number is odd. Another way to tell is if the number is divisible by 2.

Step 3 Writing out possible solutions

Now we need to write out possible solutions for our problem. In a simple problem like this, it will usually entail writing out the actual problems in language . In more complex problems, you might need to write out pseudo solutions first.

// Solution number 1

_Bool IsEven (int i) {

int x = i % 10;

if (x == 2 || x == 4 || x == 6 || x == 8 || x == 0)

return 1;

else

return 0;

}

// Solution number 2

_Bool IsEven(int i) {

if (i % 2 == 0)

return 1;

else

return 0;

}

Step 4 Deciding which solution to use

The first thing that we check is which one is cheaper; which one is more efficient? There are many machine specific ways to determine this, however, in this example it is clear that solution two is cheaper. Although we used the same amount of modulo, we used much less logical operators in that solution.

So, we have decided that checking if a number is divisible by 2 is the best method of determining if a number is even or odd. Now we’re going to make it more efficient.

Step 5 Optimizing your solution

Often times programmers who use compilers will make excuses when writing their code that there is no need for them to optimize their code, as the compiler will do this for them. That is true to a degree; which is the danger of that statement. Seeing as you are likely to use more than one compiler/optimizer, and seeing as you probably didn’t write the optimizer yourself, you probably don’t know enough about the particular optimizer to presume what it will and won’t optimize. Because of this, code that will be frequently ran, or expensive code, should be optimized by you, not just the compiler.

So, what are some ways we can optimize our solution? If we look at our code, we have 2 conditional statements (if and else) and 1 conditional operator (==). None of those are actually required.

What is the result of modulo? Given the arguments x % y, the outcome has a range of 0 to y – 1 presuming y < x. What this means is that the result of our use of modulo (the result of i % 2) will be either 0 or 1. If the result is 0, we can return 1 (remember, in C true =1), and if the result is 1, we can return 0 (false =0). Notice, we are just returning the opposite boolean value that we gain from the modulo. Instead of using if and else to return the opposite value, we can just not (!) the value returned by i % 2, which is several cycles cheaper.

// Improved solution

_Bool IsEven (int i) {

return !(i % 2);

}

We have shortened our algorithm by quite a bit! The optimization isn't done though. On a large amount of machine architects, the way modulo is achieved is by completing either division, or a form of division. Division is an extremely slow operation (about 40-90X slower than addition). So, what can we do? It just so happens that we are programming a computer. We're programming a machine that thinks in binary. It just so happens that if the first digit of a binary number is one, the number is odd, and if not, it is even! With this knowledge we can make our program tremendously faster!

// Improved^2 solution

_Bool IsEven (int i) {

return !(i & 1);

}

By replacing modulo with a logical &, we have increased the speed of our algorithm by a landslide! However, there is still another optimization we can complete. Currently, we have two operations to determine if a number is even or odd. A not, and an and. Both of these operations are extremely fast, however, the not operation isn't needed if we change our program slightly.

// Improved^3 solution

#define IsOdd(i) (i & 1)

This algorithm is now in its most optimized form. By changing the function name from IsEven to IsOdd, we no longer need to not the result of the and, this increases speed by a large amount. Also since this is such a small algorithm, we don't need to have it be a function, so we turn it into a macro and remove the expense of a function call.

Step 6 Documenting the solution

So, now we have our solution! It's smaller, more elegant, and beautiful than our original solution, however, it can still be made more elegant and beautiful, simply by the power of comments.

// ******IsOdd******

// The IsOdd macro does exactly what it sounds like it'd do, it tells if * is odd.
// We test to see if the first bit is one or zero, if the first bit is one, then is clearly odd,
// if not, it’s even.
#define IsOdd(i) (i & 1)*

Any time you’ve optimized a function, or have written a complex function, it’s a good idea to go ahead and write comments explaining what the algorithm does, and how it works.

So, what are the steps to problem solving?

Define the problem

Define potential solutions

Write out potential solutions

Decide on the solution you want to use

Optimize solution

Document solution

It’s easy to spend too little, or even too much time on any one of these tasks, and in doing so, a bit of the art in programming is taken away. Sometimes it’s important to go back to the basics and remember what we love about programming; sometimes it’s important to remember that programming is an art form; a form of expression as much as a science.