Archive for October, 2008

F# and the Euler project


At JAOO 2008 I attended the presentation “Learning F# and the Functional Point of View” by Robert Pickering. It’s been quite a while since I’ve done functional programming (I think it was when we implemented a small compiler in SML at DIKU a few years back), so this was a nice opportunity to revisit the functional paradigm. Since “real men use the stack” and since functional programming and its immutable datastructures will really come into its own when we’re talking concurrent applications and the plethora-of-processors machines of the future, it is about time we start considering using functional programming in main stream applications.

All of the above lead me to pick up F# and a book (“Foundations of F#“, also by Robert) this past weekend. In order to get a real feel for the language I decided to tackle some of the problems at Project Euler while reading the book. Thus, without further ado, here’s the Euler Project’s Problem #3 and my solution using F#:

Problem 3:
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

Solution using F#:

(comments below)

let doesNotContainAsFactors (p:bigint) xs =
(List.for_all (fun a -> not (p % a = 0I)) xs)

let rec nextPrime (x:bigint) primes =
    if doesNotContainAsFactors x primes then
        x, x::primes
        nextPrime (x+1I) primes

(* Find largest prime factor in x*)
let largestPrimeFactor x =
    let rec innerLargestPrimeFactor (x:bigint) primesLessThanCandidate candidate =
        if candidate = x then
            match x % candidate with
            | 0I -> innerLargestPrimeFactor
                (x / candidate) primesLessThanCandidate candidate
            | _ ->
                match (nextPrime candidate primesLessThanCandidate) with
                (newPrime, newPrimesList) ->
                    innerLargestPrimeFactor x newPrimesList newPrime
            innerLargestPrimeFactor x [] 2I

First, we define a function

doesNotContainAsFactors : bigint -> BigInt list -> bool.

This function takes a list of integers xs (as you can see from definition they are really bigints, but for convenience I’m going to continue to refer to them as integers) and an integer p. The function returns true if no element of xs is a divisor in p. Thus, if xs contains all primes smaller than p then doesNotContainAsFactors will return true exactly when p is a prime.
The next function to consider is

nextPrime : bigint -> BigInt list -> bigint * bigint list.

This function takes an integer x and a list primes of integers. When xs contains all the primes less than x the function uses doesNotContainAsFactors to find the first prime greater than or equal to x. It returns this prime along with a list of all primes less than or equal to the newly found prime.
Next comes the main function,

largestPrimeFactor : bigint -> bigint

which is to take an integer x and return its largest prime factor. It does this by testing whether 2 divides x. If it doesn’t, nextPrime is used to find the next prime and the test is repeated. When a prime divides x we factor out the prime by repeating the test on the quotient. Since the primes we test are continually getting larger, we will eventually have factored out all but the largest prime divisor. Once multiple occurences of this largest prime divisor have been factored out, the candidate prime we are trying to divide into x will now equal x. Thus, once we recognize that this is the case, we return x.

So, what is the largest prime factor of 600851475143?. Well, we evaluate largestPrimeFactor 600851475143I and see that the answer is 6857.

I am not entirely happy with the performance of the functions above. Finding the largest prime of 600851475143 does take a couple of seconds on my laptop. I haven’t analyzed the complexity of the code above, but it sure doesn’t feel right. That might be a topic for a future post. Also, comments are welcome :-)