Project Euler in F# – Problem 5 (alternative solution)

There was some buzz concerning my last post on Project Euler Problem 5, since the solution presented implemented a naive brute-force algorithm and its performance was very poor.

In my mind it was only meant to be an introductory article devoted to presenting a first solution to a common problem, the least common multiple (LCM) of a set of numbers, and I planned to write a second post (the one you are reading now) to show how a “smart” algorithm could lead to outstanding performance.

Let’s read the text of the exercise another time:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

As we already explained, the exercise just asks us to find the least common multiple of all numbers from 1 to 20, and we can compute it by using the greatest common divisor of these numbers.

In fact, we have that:

lcm (a,b) = a * b / gcd (a,b)

In order to compute the LCM of the numbers from 1 to 20, we start computing the LCM of the first two numbers (1 and 2) and then we go on computing the LCM of the result and the third element of the sequence. We go on this way until all elements have been included in the computation.

The application of the same function to all elements of a sequence while keeping an “accumulator” is called folding, and it is a common practice in functional programming.

Let’s look at the code:

#light
open Microsoft.FSharp.Math.BigInt

// Greater Common Divisor
let rec gcd a b =
 match b with
 | b when b = 0I -> a
 | b -> gcd b (a % b)

// Least Common Multiple
let lcm a b = a * b / (gcd a b)

let answer = Seq.fold1 lcm [1I .. 20I]

At line 11 we defined the least common multiple as explained above, while at line 5 we have the implementation of the Euclidean algorithm for the Greatest Common Divisor.

Then we simply fold the lcm function on the sequence [1 .. 20] and we get the output.

Do you remember how much time our “optimized” algorithm in the last article takes to perform the same calculation? 25 seconds.

The solution presented here only needs 15 milliseconds!

5 Comments »

claudio on February 8th 2008 in Project Euler

5 Responses to “Project Euler in F# – Problem 5 (alternative solution)”

  1. Michiel Borkent responded on 03 Mar 2008 at 6:36 pm #

    The list you feed to fold to generate the solution can be simplified itself, by observing that:

    lcm(a,b) = b when b can be written as a*n, with n being a natural number.

    Examples: lcm(5,20) = 20, lcm(2,100) = 100 etc etc

    So, instead of using the whole [1I .. 20I] use [11I; 12I; 13I; 14I; 15I; 16I; 17I; 18I; 19I; 20I]

  2. Michiel Borkent responded on 03 Mar 2008 at 6:37 pm #

    … which can of course be written as [11I .. 20I] ;-)

  3. Michiel Borkent responded on 03 Mar 2008 at 6:47 pm #

    Btw, how are you measuring the execution time? Using #time;;?

  4. claudio responded on 03 Mar 2008 at 7:21 pm #

    To measure the execution time I store the value of DateTime.Now at the beginning and the end of the script and subtract them.

    It is quite a “naive” solution but I simply wanted to get an idea of the execution time.

  5. Joel responded on 08 Dec 2009 at 10:51 am #

    For what it’s worth, this version returns the correct result in about 3.5 ms on my machine, compared to 28 ms for the code in your post. (According to System.Diagnostics.Stopwatch)

    let problem5 =
    // least common factor
    let rec lcf = function
        | hd :: tl -> hd :: lcf (List.map (fun x -> if x % hd = 0 then x / hd else x) tl)
        | [] -> []
    [1..20] |> lcf |> List.fold (*) 1

    I based the code on the algorithm described at the link below, but in F# I only needed 4 lines of code, vs 30+ lines of C#.

    http://srtsolutions.com/blogs/billwagner/archive/2008/04/08/euler-problem-5.aspx

Trackback URI | Comments RSS

Leave a Reply