Project Euler | Problem 1

Okay, so I'm going to try and learn some more languages, and improve my knowledge of those I already know. I'm going to keep a log of the code I write on this blog. I'll try and write the solution in as many languages as possible. Plus, maybe the fact that everyone can read my ugly code means I'll try and write things in a nicer way. This post-series is mostly just personal; I don't expect people to read this.

Anyway, lets get started with Problem 1. Of course, the basic solution is simple: walk over the numbers between 0 and 1000, check whether 3 or 5 divides it, add them to the sum. I figured I could play with some efficiency, but it turned out (clicky) that there is simply an x86 operator that does the modular operation, so there's not a whole lot to speed up here. Here's what I did in C:

#include 
int main(){
 int i = 0;
 int sum=0;
 while (i<1000){
  if ((i%3==0) | (i%5==0)){
   sum+=i;
  }
  i++;
 }
 printf("%d\n",sum);
}

I'm kind of bothered by the fact that I need the include. But anyway, you can also do this without a division if you really want it. it's easiest to demonstrate with python:

rresult=0
for i in range(999,0,-3):
 result+=i

for i in range(995,0,-5):
 result+=i

for i in range(15,1000,15):
 result-=i
print result

Of course, these numbers are pretty boring. I tried to scale things up a bit, so I modified the C code to use longs for the sum and had both go up to 1 000 000. Using memtime (a little tool to record time and used memory for whatever you feed it), I recorded the time each took. As expected, python is way slower:
namnatulco@namnatulco-desktop:~/codestuff$ memtime ./a.out
233333166668
Exit [0]
0.01 user, 0.00 system, 0.10 elapsed -- Max VSize = 1616KB, Max RSS = 56KB
namnatulco@namnatulco-desktop:~/codestuff$ memtime python test.py
233333166668
Exit [0]
0.27 user, 0.00 system, 0.40 elapsed -- Max VSize = 12472KB, Max RSS = 8544KB

However, if I change the python code to match what the C code does, this happens:
namnatulco@namnatulco-desktop:~/codestuff$ memtime python test.py
233333166668
Exit [0]
0.74 user, 0.00 system, 0.80 elapsed -- Max VSize = 7212KB, Max RSS = 3312KB

Surprising? Perhaps at first, yes. But if you know a little bit about python, you'll know it has a lot of C in the background. Looks like even though the range() function takes a large amount of memory, it's way faster than manual computation.

So that's it. Enough toying with code; go listen to this magnificent post-hardcore album:

There's a sample track (Vulgar Theories) for listening on the dischord website (take note: flash).