CODEWITHSUNDEEP
performancef#functional-programming
zmbq
zmbq

Reputation: 39023

Using Functional Programming to compute prime numbers efficiently

I'm getting acquainted with F# by going over Project Euler and solving some of the problems. Many of the early problems consist of prime numbers. After looking around I came up with the following solution:

let primesL =
    let rec prim n sofar = 
        seq { if (sofar |> List.forall (fun i->n%i <>0L)) then
                  yield n
                  yield! prim (n+1L) (n::sofar)
              else
                  yield! prim (n+1L) sofar  }
    prim 2L []

This works well, but then I generate all the prime numbers up to 2000000:

let smallPrimes = primesL |> Seq.takeWhile (fun n->n<=2000000)

This takes ages. It's quite obvious something is done in O(N^2) or worst.

I know I can write an imperative version and implement a sieve of some sort, but I want to stick to functional code. If I wanted imperative, I would have stayed with C#.

What am I missing?

Upvotes: 5

Views: 2438

Answers (5)

Norman Ramsey
Norman Ramsey

Reputation: 202595

Rather than write a long answer here, I refer you to Melissa O'Neill's great paper on the sieve of Eratosthenes.

Upvotes: 8

Gene Belitski
Gene Belitski

Reputation: 10350

You may want to compare your approach with my variant of Problem Euler 10 solution

let rec primes = 
    Seq.cache <| seq { yield 2; yield! Seq.unfold nextPrime 3 }
and nextPrime n =
    if isPrime n then Some(n, n + 2) else nextPrime(n + 2)
and isPrime n =
    if n >= 2 then
        primes 
        |> Seq.tryFind (fun x -> n % x = 0 || x * x > n)
        |> fun x -> x.Value * x.Value > n
    else false

It is purely functional, uses sequence cashing, optimized for primality check; also it yields very useful isPrime n function as a co-result.

And being applied to the original problem

let problem010 () =
    primes
    |> Seq.takeWhile ((>) 2000000)
    |> (Seq.map int64 >> Seq.sum)

it completes in decent 2.5 s. This is not blasting fast, but was good enough to use this primes sequence in handful of my other Project Euler solutions (27, 35, 37, 50, 58, 69, 70, 77 so far).

As to what you're missing in your solution - from your code I believe you're building a brand new sequence on each internal call to prim, i.e. for each natural while my approach uses a single sequence for already found primes and only enumerates its cached instance when producing each next prime.

Upvotes: 6

John Palmer
John Palmer

Reputation: 25516

What you really want here is a sieve - I have written a pretty fast F# sieve before here:

F# parallelizing issue when calculating perfect numbers?

Upvotes: 1

BLUEPIXY
BLUEPIXY

Reputation: 40145

Use "Miller–Rabin primality test" for more than some large prime number

Upvotes: -1

Ramon Snir
Ramon Snir

Reputation: 7560

First, it is O(n^2) - remember that you use List.forall on each iteration.

Second, if you use the generator a lot, you should cache the results (so that each prime number is only calculated once):

let primesL =
    let rec prim n sofar = 
        seq { if (sofar |> List.forall (fun i -> n % i <> 0UL)) then
                  yield n
                  yield! prim (n + 1UL) (n::sofar)
              else
                  yield! prim (n + 1UL) sofar }
    prim 2UL []
    |> Seq.cache

Upvotes: 1

Related Questions