finding primes very slow in F#

Question

I have answered Project Euler Question 7 very easily using Sieve of Eratosthenes in C and I had no problem with it.

I am still quite new to F# so I tried implementing the same technique

let prime_at pos =
  let rec loop f l =
    match f with 
    | x::xs -> loop xs (l |> List.filter(fun i -> i % x <> 0 || i = x))
    | _ -> l

  List.nth (loop [2..pos] [2..pos*pos]) (pos-1)

which works well when pos < 1000, but will crash at 10000 with out of memory exception

I then tried changing the algorithm to

let isPrime n = n > 1 && seq { for f in [2..n/2] do yield f } |> Seq.forall(fun i -> n % i <> 0)

seq {for i in 2..(10000 * 10000) do if isPrime i then yield i} |> Seq.nth 10000 |> Dump

which runs successfully but still takes a few minutes.

If I understand correctly the first algorithm is tail optimized so why does it crash? And how can I write an algorithm that runs under 1 minute (I have a fast computer)?

Answer 1

Looking at your first attempt

let prime_at pos =
  let rec loop f l =
    match f with 
    | x::xs -> loop xs (l |> List.filter(fun i -> i % x <> 0 || i = x))
    | _ -> l

  List.nth (loop [2..pos] [2..pos*pos]) (pos-1)

At each loop iteration, you are iterating over and creating a new list. This is very slow as list creation is very slow and you don't see any benefits from the cache. Several obvious optimisations such as the factor list skipping the even numbers, are skipped. When pos=10 000 you are trying to create a list which will occupy 10 000 * 10 000 * 4 = 400MB of just integers and a further 800MB of pointers (F# lists are linked lists). Futhermore, as each list element takes up a very small amount of memory there will probably be significant overhead for things like GC overhead. In the function you then create a new list of smiliar size. As a result, I am not surprised that this causes OutOfMemoryException.

Looking at the second example,

let isPrime n = 
    n > 1 && 
    seq { for f in [2..n/2] do yield f } 
    |> Seq.forall(fun i -> n % i <> 0)

Here, the problem is pretty similar as you are generating giant lists for each element you are testing.

I have written a quite fast F# sieve here https://stackoverflow.com/a/12014908/124259 which shows how to do this faster.