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

Post date: Sep 9, 2009 9:12:28 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