Nsryjdtyk

I'm using Exercism to learn F#. The Nth Prime challenge was to build a Sieve of Eratosthenes. The unit test had you search for the 1,001st prime which is 104,743.

I modified a code snippet I remembered from F# For Fun and Profit to work in batches (need 10k primes, not 25) and compared it to my own imperative version. There is a significant performance difference:

(BenchmarkDotNet v0.11.2)

Is there an efficient way to do this idiomatically? I like F#. I like how much time using the F# libraries save. But sometimes I can't see an efficient idiomatic route.

Here is the idiomatic code:

// we only need to check numbers ending in 1, 3, 7, 9 for prime

let getCandidates seed = 

    let nextTen seed ten = 

        let x = (seed) + (ten * 10)

        [x + 1; x + 3; x + 7; x + 9]

    let candidates = [for x in 0..9 do yield! nextTen seed x ]

    match candidates with 

    | 1::xs -> xs  //skip 1 for candidates

    | _ -> candidates





let filterCandidates (primes:int list) (candidates:int list): int list = 

    let isComposite candidate = 

        primes |> List.exists (fun p -> candidate % p = 0 )

    candidates |> List.filter (fun c -> not (isComposite c))



let prime nth : int option = 

    match nth with 

        | 0 -> None

        | 1 -> Some 2

        | _ ->

            let rec sieve seed primes candidates = 

                match candidates with 

                |  -> getCandidates seed |> filterCandidates primes |> sieve (seed + 100) primes //get candidates from next hunderd

                | p::_ when primes.Length = nth - 2 -> p //value found; nth - 2 because p and 2 are not in primes list

                | p::xs when (p * p) < (seed + 100) -> //any composite of this prime will not be found until after p^2

                    sieve seed (p::primes) [for x in xs do if (x % p) > 0 then yield x]

                | p::xs -> 

                    sieve seed (p::primes) xs





            Some (sieve 0 [3; 5] )

And here is the imperative:

type prime = 

    struct 

        val BaseNumber: int

        val mutable NextMultiple: int

        new (baseNumber) = {BaseNumber = baseNumber; NextMultiple = (baseNumber * baseNumber)}

        //next multiple that is odd; (odd plus odd) is even plus odd is odd

        member this.incrMultiple() = this.NextMultiple <- (this.BaseNumber * 2) + this.NextMultiple; this 

    end



let prime nth : int option = 

    match nth with 

    | 0 -> None

    | 1 -> Some 2

    | _ ->

        let nth' = nth - 1 //not including 2, the first prime

        let primes = Array.zeroCreate<prime>(nth')

        let mutable primeCount = 0

        let mutable candidate = 3 

        let mutable isComposite = false

        while primeCount < nth' do



            for i = 0 to primeCount - 1 do

                if primes.[i].NextMultiple = candidate then

                    isComposite <- true

                    primes.[i] <- primes.[i].incrMultiple()



            if isComposite = false then 

                primes.[primeCount] <- new prime(candidate)

                primeCount <- primeCount + 1



            isComposite <- false

            candidate <- candidate + 2



        Some primes.[nth' - 1].BaseNumber

So in general, when using functional idioms, you probably expect to be a bit slower than when using the imperative model because you have to create new objects which takes a lot longer than modifying an already existing object.

For this problem specifically the fact that when using an F# list, the fact that you need to iterate the list of primes every time is a performance loss compared to using an array. You should also note you don't need to generate a candidate list separately, you can just loop and add 2 on the fly. That said the biggest performance win is probably using mutation to store your nextNumber.

type prime = {BaseNumber: int; mutable NextNumber: int}

let isComposite (primes:prime list) candidate = 

    let rec inner primes candidate =

        match primes with 

        |  -> false

        | p::ps ->

            match p.NextNumber = candidate with

            | true -> p.NextNumber <- p.NextNumber + p.BaseNumber*2

                      inner ps candidate |> ignore

                      true

            | false -> inner ps candidate

    inner primes candidate





let prime nth: int option = 

    match nth with 

    | 0 -> None

    | 1 -> Some 2

    | _ -> 

            let rec findPrime (primes: prime list) (candidate: int) (n: int) = 

                match nth - n with 

                | 1 -> primes

                | _ -> let isC = isComposite primes candidate

                       if (not isC) then

                           findPrime ({BaseNumber = candidate; NextNumber = candidate*candidate}::primes) (candidate + 2) (n+1)

                       else

                           findPrime primes (candidate + 2) n

            let p = findPrime [{BaseNumber = 3; NextNumber = 9};{BaseNumber = 5; NextNumber = 25}] 7 2

                    |> List.head

            Some(p.BaseNumber)

Running this through #time, I get around 500ms to run prime 10001. For comparison, your "imperative" code takes about 250ms and your "idomatic" code takes around 1300ms.

At first glance you're not comparing equal concepts. Of course, I'm not talking about functional vs imperative, rather the concepts behind the algorithms themselves.

Your wiki reference says it best:

This is the sieve's key distinction from using trial division to sequentially test each candidate number for divisibility by each prime.

In other words, the Sieve of Eratosthenes' power lies in not using trial division. Another wiki ref:

Trial division is the most laborious but easiest to understand of the integer factorization algorithms.

And is effectively what you're doing in your filter.

let isComposite candidate =  

    primes |> List.exists (fun p -> candidate % p = 0 )