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))

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)

(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:

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....

sure.

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

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

Post a Comment