How to Solve It: Mathematical Approach to Programming

In this blog post, I would like to extend concepts previously discussed in my previous post - problem solving with a mathematical approach.

Every day, we tackle problems more complex than those we’ve previously solved. In this blog post, I would like to extend concepts previously discussed in my post about the secrets to a successful juniorship. While studying mathematics, I read a book named “How to solve it”, about simplifying complex problems. It was about heuristics - very direct (though not necessarily the most efficient) ways of getting solutions.

This blog post presents some heuristics discussed by George Pólya, the great Hungarian mathematician. We’ll talk about some successful approaches for finding solutions. Pólya completely changed my approach to solving problems. Not only mathematical ones - his ideas can be successfully applied to other fields, including computer science. I am going to explain how we can use these heuristics in programming and give examples that show how they work in real code. I invite you to read Pólya and try to find your own solutions. The sample code is written in Ruby, don’t forget about that!

Pay attention, here are the rules

Below I present the basics steps from Pólya’s book with short comments. I find these little things extremely helpful when seeking solutions:

1. Understand the problem

Read the task carefully, try to understand it, and think about it deeply. Think about what you have and what you want to find. Phrase the task in your own words.

2. Form an algorithm

Find the relation between the information given and what you want to find. In same cases, it will be much easier to solve a slightly different problem if you can't find the solution directly. At the end of your work, you should have made an algorithm to solve the problem. Imagine a function as a black box where you input some information and later get it back in some changed shape.

Think about some similar problem. Perhaps you’ve solved something similar and you can re-use the solution in a slightly different way, with a slightly different approach. How can you transform your data? What kind of data structure do you need? What parameters do you need to pass through functions? Think about the data structure which you have, maybe it has a special structure which allows you to use some suitable algorithms.

3. Just make an algorithm!

Move step by step and see if you can prove each step. Do something that makes sense. Don’t just mindlessly repeat yourself. A good algorithm defends itself. Now you can write a program to solve it.

4. Look back at your solution

A second look allows you to find more efficient solutions. After you find an answer - think if it can be done better. Sometimes the improvements are tenuous and uncertain, usually they’ll allow you to write more efficient programs and care about better time complexity. Feedback gives you both positive and negative information. It lets you see your strengths and your weaknesses, so you can know the areas where you need to work to improve at. Next time when you are faced with a problem, you’ll be able to solve it faster and better.

How does it work?

Let's write a program which computes the nth Fibonacci number and then for two neighbouring such numbers, find a way to compute their greatest common divisor, gcd(F(n),F(n+1)) = ?.

Understand

What do you need? The greatest common divisor of two Fibonacci numbers.

How do you get it? Write a generic function to compute Fibonacci numbers for a given variable.

What type of variable do we need? It must be an integer

Do we need anything else? Yes, a function for the greatest common divisor.

Make a plan

My plan is pretty short:

I am going to write a Fibonacci function - I need a formula for it, and it will be a recurrence function. Next, I will write a function which finds the greatest common divisor (gcd) of two numbers. Finally, put the first into the second and I’ll get the greatest common divisor of two Fibonacci numbers.

I present the function based on the formula, and it is pretty simple. The first and second number in the sequence equals one, and each next element is the sum of the two previous elements in the sequence. For more details see Fibonacci number (on Wikipedia).

Now, the gcd function

Execute it

For given n

For instance n = 32

You can use a debugger to move step by step and check how this function works - this is useful when something goes wrong.

Look back

What can I do better? I think the Fibonacci function is not efficient enough. I can compute an array and then choose neighboring entries.

This function returns n Fibonacci numbers in an array:

and the following function returns an array of two neighbouring numbers

then I can connect these two functions and use a splat operator to pass parameters to the gcd function.

It should return '1' if the numbers have not got a common divisor. It is a faster solution than the previous one with recurrence and doesn’t require as much computation.

Returning to Pólya

I return to his books because I always find something new with each new reading. In the 20th, century the idea of the hermeneutic circle was first discussed. It describes the simple observation that each time when we read a text, the previous reading changes the current one. As a result, we get a better and deeper understanding of the idea of the text. When we apply this to Pólya’s heuristics, we get strong and useful equipment that we can use in our work. Also, his book contains a dictionary of heuristics, I think a curious reader will find in it a lot of helpful tactics and blocker-breakers.

A goodbye

To finish up - you should check if the greatest common divisor of all neighbouring Fibonacci numbers is 1. I’ll leave you with a quote from another excellent mathematician, Paul Halmos, which shows the remarkable importance of questions and is a good summary of this post:

Don't just read it; fight it! Ask your own questions, look for your own examples, discover your own proofs. Is the hypothesis necessary? Is the converse true? What happens in the classical special case? What about the degenerate cases? Where does the proof use the hypothesis?