F# why my recursion is faster than Seq.exists?

Posted by user38397 on Stack Overflow See other posts from Stack Overflow or by user38397
Published on 2012-09-12T03:24:31Z Indexed on 2012/09/12 3:38 UTC
Read the original article Hit count: 121

Filed under:
|
|

I am pretty new to F#. I'm trying to understand how I can get a fast code in F#. For this, I tried to write two methods (IsPrime1 and IsPrime2) for benchmarking. My code is:

// Learn more about F# at http://fsharp.net
open System
open System.Diagnostics

#light

let isDivisible n d = n % d = 0
let IsPrime1 n =
    Array.init (n-2) ((+) 2) |> Array.exists (isDivisible n) |> not

let rec hasDivisor n d =
    match d with
    | x when x < n -> (n % x = 0) || (hasDivisor n (d+1)) 
    | _ -> false

let IsPrime2 n =
    hasDivisor n 2 |> not


let SumOfPrimes max = 
    [|2..max|] |> Array.filter IsPrime1 |> Array.sum

let maxVal = 20000

let s = new Stopwatch()
s.Start()

let valOfSum = SumOfPrimes maxVal

s.Stop()

Console.WriteLine valOfSum
Console.WriteLine("IsPrime1: {0}", s.ElapsedMilliseconds)

//////////////////////////////////
s.Reset()
s.Start()

let SumOfPrimes2 max = 
    [|2..max|] |> Array.filter IsPrime2 |> Array.sum

let valOfSum2 = SumOfPrimes2 maxVal

s.Stop()

Console.WriteLine valOfSum2
Console.WriteLine("IsPrime2: {0}", s.ElapsedMilliseconds)

Console.ReadKey()

IsPrime1 takes 760 ms while IsPrime2 takes 260ms for the same result. What's going on here and how I can make my code even faster?

© Stack Overflow or respective owner

Related posts about Performance

Related posts about F#