Just Code‎ > ‎

F# Sieve of erastothenes, two versions: List and Seq. Interesting performance differences

posted Sep 9, 2009, 2:12 AM by Peter Henell   [ updated Sep 9, 2009, 3:59 AM ]
let sieveOfErat max =
    
    let rec sieve l r =
        let r = List.Cons (List.hd l, r)
        let l = List.filter(fun x -> (x % r.Head <> 0I && x <> r.Head)) l
        match r.Head with
        | n when n > bigint.FromInt32(int (Math.Ceiling(Math.Sqrt (big_int.ToDouble max)))) -> List.append l r
        | n ->      
           match (List.length l) with
           | 0 -> r
           | n -> sieve l r
           
    sieve [2I..max] []
    
    
let sieveOfEratSeq max =
    
    let rec sieve l r =
        let r = Seq.cons (Seq.hd l) r
        let l = Seq.filter(fun x -> (x % (Seq.hd r) <> 0I && x <> (Seq.hd r))) l
        match (Seq.hd r) with
        | n when n > bigint.FromInt32(int (Math.Ceiling(Math.Sqrt (big_int.ToDouble max)))) -> Seq.append l r
        | n ->      
           match (Seq.length l) with
           | 0 -> r
           | n -> sieve l r
           
    sieve {2I..max} Seq.empty
Comments