Sunday, November 20, 2011

Math and Algorithm Programming with Project Euler

If you're a web developer or other type of programmer that doesn't require much math, you might be pretty weak with math based programming. Doing Project Euler problems will help to strengthen your math and algorithm programming abilities.

From the official website for Project Euler:

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

The way it works is you register for free on the site then it gives you problems such as "Calculate the sum of all the primes below two million." Your task is to implement an algorithm in the programming language of your choice to give you the answer. Once you have the answer, you paste it into the web site and then it tells you if you got the answer correct or not. If you answered correctly it gives you the ability to view other programmer's source code for how they did it and even submit your own if you want to.

I recommend doing some of the problems as code katas. A code kata is a way of practicing typing out low-level programming problems over and over until it becomes second nature to you--just like doing doing martial arts katas helps martial artists. I still remember some of the katas from martial arts that I haven't done in over 10 years. Repetition truly is the mother of all skill.

Another thing that doing Euler problems will help you with is learning how to optimize algorithms. The speed of the machine your program runs on will largely affect the speed of your programs, but you often don't realize it until you're doing an algorithm on some large numbers. Fortunately, many Euler problems will really push you and your machine.

You optimize the algorithms by benchmarking the program and refactoring it to run faster and faster. Sometimes you'll need to use a different math library to speed things up. For example, bcmath is a lot faster than the regular math functions in PHP for me.

How do you benchmark? The easiest way is to use the time command, which is available for Unix-like operating systems such as Linux and OS X:
 $ time ./my-program
You should also try profiling your solutions. Ruby comes with a built-in code profiler if you give it the -rprofile argument, but it's rather slow. I prefer to install ruby-prof. So I can profile with:
 $ ruby-prof ./my-program.rb
Profiling is great because it will tell you exactly which part of your code is taking the longest to run, so you can focus on optimizing just the bottlenecks.

I highly recommend solving the same problems in different languages. This will not only help teach you other languages, it will show you how much faster or slower a language is compared to other languages. It will also show you how expressive one language is compared to another. Sometimes I use the exact same algorithm in C as I do in PHP, and the syntax is almost completely identical, only the C version runs light years faster, of course.

It's worth running your solved problem using different versions of the same language. For example, PHP 5.3 solves my Euler problems a lot faster than php 5.2. Ruby 1.9 solves them a lot faster than 1.8, and so on.

I solved a lot of Euler problems between 2007 and 2010. When I recently looked back at some old problems I solved, one thing that I'm really glad I did back then was write comments to myself in each source file telling me: 1) How long it took me to solve the problem 2) How fast it ran on whatever machine and language version I was using at the time and 3) which language I solved it in first.

One last thing; make sure you go to projecteuler.NET and not the .com. The .com is a really annoying spam website.