Problem 127
It was over a year ago now… Project Euler - I was in the top 10, then they posted Problem 127. All of the problems there should execute in under the minute, and I thought I had optimized my code, but it was running for many minutes when I stopped it to see what was going on. I instrumented my code to see and saw that it was just chugging away. It would have taken 10-ish hours to complete! What was the problem? Python.
Quite a few of the problems at Project Euler require numbers to be larger than 32 bits. I originally used Project Euler to teach myself Python, and Python deals with big numbers fairly easily in code. My language of choice at the time, C/C++/Asm, didn’t. Even in Python, an interpretted language, I was able to get most of my solutions to run in under a minute - and that was the goal. Every so often, like times where the code iterated over large arrays, or basically anything that had a large number of real operations that had to be performed, I would have to switch back to C/C++. If the solution was taking minutes to run under Python, it would complete in a second or two under C/C++. But the time I saved writing the code in Python for the cases it could solve was worth it.
Now I have F# - my new favorite language. It also has big number support built in (so does Erlang). I was able to recode my old solution from memory from last year, and suddenly, I had a solution in under a minute! Well, it took a bit of work, since I had a bug in my code - I missed an overflow, so it was doing way to many calculations - it was taking minutes to generate the wrong answer. (comparing numbers to see if a calculation needed to be done, but the numbers being compared overflowed, so it was always doing the calculation, which was very slow as well as incorrect)
Some important things I learned from this year-ish journey:
1) People always tell me that only the order of the algorithm matter, linear speed ups will be swamped by faster machines. If the linear is hundreds, thousands, or millions, that is false. Rewriting critical code in a compiled or assembly language will always be of use.
2) Numbers shouldn’t have ranges. The overflow bug that cost me a day wouldn’t have existed if the language could handle numbers cleanly, not just integers. I had written the code in Erlang last night, but it was too slow to complete (linked lists as were the killer there). Erlang transparently works with all numbers, so that code couldn’t have that bug. Couldn’t. Bug-free code is the goal, so the languages need to handle these types of things transparently.
3) Getting things done is important. I used Python because it was trivial to write most of the code needed for Project Euler. The code only had to execute once (well, I reused a lot of it, so it had to execute once per problem), so optimizing my time speeds up the time from start to answer-in-hand. And that is what programming is about, getting the correct answer as quickly as possible.
-Edward
April 10th, 2008 at 2:41 pm
PS Something I’ve heard/said: If you don’t care about accuracy, you can make your code as fast as you want. I found out today this is also true: If you don’t care about accuracy, you can make your code as slow as you want.