Project Euler in F#: Problem 1

After spending the past year doing pure theory, I really miss programming. I probably ought to do something in a language I’m familiar with, but I can never resist learning something new, so I’m going to try to learn F# by working through Project Euler.

One of the best ways to get better at coding is to have someone else review your code. Unfortunately, I’m not in an environment where I can get that kind of feedback. I got some nice suggestions by posting a code snippet to stackoverflow, but I’d feel ridiculous making a hundred stackoverflow posts about Project Euler problems. Luckily, people often seem willing to play code golf with Project Euler solutions posted on blogs; I’m hoping people will show me up by posting more elegant (or more optimized solutions) that I can learn from.

The problem is:

Add all the natural numbers below 1000 that are multiples of 3 or 5.

My first solution was:

let ans = seq {for i in 1 .. 999 do if i % 3 = 0 || i % 5 = 0 then yield i} |> Seq.sum

That worked fine, but after paging through Programming F# I realized that I could write this more simply as

let altAns = {1..999} |> Seq.filter (fun n -> n % 3 = 0 || n % 5 = 0) |> Seq.sum

This runs quickly enough that optimization doesn’t matter, but I was curious if the first solution would be faster if the problem were big enough that it mattered. Much to my surprise, if you increase the range so that it’s large enough that performance actually matters (say, {1I..999999I} instead of {1..999}, the second solution is measurably faster (2.3s vs 3.0s on my 1.8Ghz C2D). I’d like to figure out how I can look at .NET CIL code, so I can see what the difference is between the two solutions.

Another reason I’d like to see the CIL code is because I’m curious how (and if) that solution differs from the following

let altAns2 = Seq.sumBy (fun n -> if n % 3I = 0I || n % 5I = 0I then n else 0I)

I had to increase the problem size by another order of magnitude and run it for a number of iterations before seeing a statistically significant difference in runtime. Re-running an experiment until you get data that lets you reject the null hypothesis is a bit bogus, though, so I’m not convinced that the second and third solution actually compile to something different (although it’s plausible that they might).
I also tried benchmarking the equivalent solution using lists, which was substantially slower, as expected. Phew! At least one of my intuitions was correct.

Of course, if we were really concerned about optimization, we could use the familiar identity: \sum i = \frac{n (n+1)}{2}, combined with the inclusion-exclusion principle, to get a closed form formula, but that wouldn’t help me learn F# :-)

Advertisements
Project Euler in F#: Problem 1

One thought on “Project Euler in F#: Problem 1

  1. […] UnlikeĀ problem 1, there are no performance surprises here: both of these solutions have the same performance, as does using Seq.initInfinite. Of course, the performance could be improved by getting rid of the mod operation and only generating the even numbers (which is easy to do, since every third item in the sequence is even). Comments RSS feed […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s