Friday, October 29, 2010

Problem: Euler task 1


From Euler project, task 1.


"If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000."


Pretty Simple:


(1 to 1000).filter( x => (x %3 == 0) || ( x%5 == 0) ).
            foldLeft(0)(_ + _)

or:

(1 to 1000).foldLeft(0)
   ( (x,y) => x + (if (y % 3 == 0 || y % 5 ==0) y else 0))


The first looks better since the addition is only done when the number is divided by 3 or 5. The second one always executes the addition and the comparison.

However, the first one creates the list of number divided by 3 or 5 first before folding.

So, I think that the second version is better in term of number of created list.

Anyway, I think the following is the best one:

(1 to 1000 / 3).foldLeft(0)( _ + _ * 3) + 
(1 to 1000 / 5).foldLeft(0)( _ + _ * 5) -
(1 to 1000 / 15 ).foldLeft(0)( _ + _ *15)


The first two versions execute 1000 comparisons inside the (1 to ...) , while the second has no comparison. So, I believe the last version should be better than the first two.


In conclusion, my guess of the best performing implementation is the following:
1. Third implementation.
2.  Second implementation.
3.  First implementation.

Maybe the first implementation performs better than the second but the first consumes more memory.

Quick profiling on time of average execution , using 1000 000 as limit instead of 1000 in my machine: 
1. First implementation: 130 ms
2. Second implementation: 65 ms
3. Third implementation: 32 ms.

Finally, I found this one as even more better solution:

(1 to 1000 / 3).foldLeft(0)( _ + _ * 3) + (
 1 to 1000/ 5).foldLeft(0)( 
   (x,y) => x + (if (y % 3 ==0) 0 else (y * 5)))

Any thought ?

2 comments:

Reza said...

Wouldn't it be faster to actually calculate them?
knowing that between 1 and 10 the multiples of 3 are
3,6,9 or
3*1 + 3*2 + 3*3
= 3*(1+2+3)
or 3* (1+k) * k/2
We can calculate based on any n:
k1 = n/3
k2 = n/5
k3 = n/15 (multiples of 15 which are both divisible by 3 and 5 are counted twice, so we need to substract it)
therefore x = 3*(1+k1)*k1/2 + 5*(1+k2)*k2/2 - 15*(1+k3)*k3/2

It's cheating :) if you really want to work with loops but hey....

voidmainargs said...

sure.

it's also challenging to compute it analytically, but my challenge was to count it programmatically.

btw, it's not really a loop :-)