Version française
Home     About     Download     Resources     Contact us    
Browse thread
[Caml-list] productivity improvement
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Markus Mottl <markus@o...>
Subject: Re: Sieve of Eratosthenes Performance: various languages (Re: [Caml-list] productivity improvement)
On Wed, 10 Jul 2002, Oleg wrote:
> Compiled with g++-3.0 -O2 on my aging AMD K6-2 550 MHz, I get
> 
> real    0m4.632s
> user    0m3.290s
> sys     0m0.260s

Here is a very fast version, which you'll probably find difficult to
beat using C:

---------------------------------------------------------------------------
let count =
  let count = ref 100 in
  let n_opt = "-n", Arg.Int ((:=) count), "nth prime (default 100)"
  and usage = "Usage: fsieve [-n number] calculates primes" in
  Arg.parse [n_opt] (fun _ -> raise (Arg.Bad "unknown argument!")) usage;
  !count

let primes =
  let primes = Array.create (max count 3) 0 in
  primes.(0) <- 2; primes.(1) <- 3; primes.(2) <- 5; primes

let rec is_prime i pr bd =
  let p = primes.(i) in p > bd || pr mod p <> 0 && is_prime (i + 1) pr bd

let get_psize psize nr bd =
  if is_prime 2 nr bd then begin primes.(psize) <- nr; psize + 1 end
  else psize

let rec prime_n psize nr tog bd bd2 =
  if psize < count then
    if bd2 <= nr then
      let bd = bd + 1 in
      prime_n (get_psize psize nr bd) (nr + tog) (6 - tog) bd (bd * bd)
    else prime_n (get_psize psize nr bd) (nr + tog) (6 - tog) bd bd2

let _ =
  prime_n 3 7 4 3 9;
  Array.iter (Printf.printf "%d\n") primes
---------------------------------------------------------------------------

Timing of ("time ocaml fsieve.ml -n 10000") on an AMD 800MHz, interpreted:

  real    0m0.586s
  user    0m0.460s
  sys     0m0.030s

Compiled to native code (-unsafe -noassert):

  real    0m0.207s
  user    0m0.100s
  sys     0m0.020s

Regards,
Markus Mottl

-- 
Markus Mottl                                             markus@oefai.at
Austrian Research Institute
for Artificial Intelligence                  http://www.oefai.at/~markus
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners