https://bitbucket.org/WilliamMayor/projecteulerIt's a Mercurial repo so you'll need to get hg installed if you don't have it already but instructions are given on bitbucket so clone away.
Monday 13 June 2011
U Can Has Teh Code Nao
I hadn't thought to pass out the URL to the repository that I'm keeping my Project Euler code in. Seems like a good idea if people are interested, so here it is:
Tuesday 7 June 2011
Problem 1
Okay, so to start of I'd thought I'd go from the beginning and try my luck with problem 1:
What is the sum of all the multiples of 3 or 5 below 1000.
This one seems pretty easy and coming up with a solution didn't take me too long at all, my first attempt was simply to do this:
sum = 0
for every number between 1 and 1000
if the number is a multiple of 5 or 3
sum += number
This definitely works as the answer it spews out was enough for me to get my first tick on the Project Euler site. Exciting. I went to bed happy.
I began to think over the next day that the point of the challenge was not to simply solve the problem but to really think about it and come up with the 'best' solution. I became convinced on my train ride home that what I had didn't cut the mustard and I had a plan to help me improve. I would time the execution of my solution and then try to best my time.
One small problem was that the solution takes 0.0 milliseconds when timed with System.currentTimeMillis() (I'm a Java guy). Rather than play around with using smaller and smaller units I decided to up the range of the problem until the 'old' solution took a decent chunk of time. So I rephrased the question to be:
What is the sum of all the multiples of 3 or 5 below Integer.MAX_VALUE (2 147 483 647)
Solving this took ~9.5 seconds and gave the answer -787410670 (*giggle*, integer overflow). Now I just had to improve the solution.
The most striking problem is that I run a maximum of 3 comparisons for every integer (one for the for loop and two for the multiplicity checks) and that the comparisons aren't trivial (modulo arithmetic FTW). This problem has a decent solution in that I can generate the required numbers rather than check every number to see if it matches:
fivemultiple = 5
threemultiple = 3
sum = 0
while fivemultiple < MAX
sum += fivemultiple
fivemultiple += 5
while threemultiple < MAX
repeat 4 times
sum += threemultiple
threemultiple += 3
threemultiple += 3
The repeat 4 times hassle at the end is to counter the fact that I now generate numbers that are multiples of both 3 and 5 twice.
Solution two solves the new problem in a modest ~0.95 seconds, a tenth of the original.
I had a facepalm moment when I realised that I could shave off more time by generating the three multiples first then the fives (now I only repeat the fiddly bit twice).
Solution three solves the new problem in ~0.39 seconds that's less than one twentieth of the original solution's time.
I'm going to read the forums soon to see how I could improve on this. For the second evening in a row though, I'm going to bed happy.
What is the sum of all the multiples of 3 or 5 below 1000.
This one seems pretty easy and coming up with a solution didn't take me too long at all, my first attempt was simply to do this:
sum = 0
for every number between 1 and 1000
if the number is a multiple of 5 or 3
sum += number
This definitely works as the answer it spews out was enough for me to get my first tick on the Project Euler site. Exciting. I went to bed happy.
I began to think over the next day that the point of the challenge was not to simply solve the problem but to really think about it and come up with the 'best' solution. I became convinced on my train ride home that what I had didn't cut the mustard and I had a plan to help me improve. I would time the execution of my solution and then try to best my time.
One small problem was that the solution takes 0.0 milliseconds when timed with System.currentTimeMillis() (I'm a Java guy). Rather than play around with using smaller and smaller units I decided to up the range of the problem until the 'old' solution took a decent chunk of time. So I rephrased the question to be:
What is the sum of all the multiples of 3 or 5 below Integer.MAX_VALUE (2 147 483 647)
Solving this took ~9.5 seconds and gave the answer -787410670 (*giggle*, integer overflow). Now I just had to improve the solution.
The most striking problem is that I run a maximum of 3 comparisons for every integer (one for the for loop and two for the multiplicity checks) and that the comparisons aren't trivial (modulo arithmetic FTW). This problem has a decent solution in that I can generate the required numbers rather than check every number to see if it matches:
fivemultiple = 5
threemultiple = 3
sum = 0
while fivemultiple < MAX
sum += fivemultiple
fivemultiple += 5
while threemultiple < MAX
repeat 4 times
sum += threemultiple
threemultiple += 3
threemultiple += 3
The repeat 4 times hassle at the end is to counter the fact that I now generate numbers that are multiples of both 3 and 5 twice.
Solution two solves the new problem in a modest ~0.95 seconds, a tenth of the original.
I had a facepalm moment when I realised that I could shave off more time by generating the three multiples first then the fives (now I only repeat the fiddly bit twice).
Solution three solves the new problem in ~0.39 seconds that's less than one twentieth of the original solution's time.
I'm going to read the forums soon to see how I could improve on this. For the second evening in a row though, I'm going to bed happy.
Intro
Hello
My name is William Mayor (Billy), I'm a UCL student currently in between courses; I've just finished a BSc in Computer Science, results pending.
In order to sharpen my programming and maths skills (and to have fun), I'm participating in the GDC's "12 Problems in 12 Weeks" Project Euler Challenge.
This blog will chronicle my rise to fame and power via the sucessful completion of the problems. Wish me luck.
My name is William Mayor (Billy), I'm a UCL student currently in between courses; I've just finished a BSc in Computer Science, results pending.
In order to sharpen my programming and maths skills (and to have fun), I'm participating in the GDC's "12 Problems in 12 Weeks" Project Euler Challenge.
This blog will chronicle my rise to fame and power via the sucessful completion of the problems. Wish me luck.
Subscribe to:
Posts (Atom)