From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id WAA18486; Wed, 10 Jul 2002 22:49:08 +0200 (MET DST)
X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f
Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id WAA18482 for <caml-list@pauillac.inria.fr>; Wed, 10 Jul 2002 22:49:07 +0200 (MET DST)
Received: from fichte.ai.univie.ac.at (fichte.ai.univie.ac.at [131.130.174.156])
	by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id g6AKn6b15078
	for <caml-list@inria.fr>; Wed, 10 Jul 2002 22:49:07 +0200 (MET DST)
Received: (from markus@localhost)
	by fichte.ai.univie.ac.at (8.9.3/8.9.3/Debian 8.9.3-21) id WAA20600;
	Wed, 10 Jul 2002 22:48:59 +0200
Date: Wed, 10 Jul 2002 22:48:59 +0200
From: Markus Mottl <markus@oefai.at>
To: Oleg <oleg_inconnu@myrealbox.com>
Cc: sebastien FURIC <sebastien.furic@tni-valiosys.com>,
        Shannon --jj Behrens <jjinux@yahoo.com>, caml-list@inria.fr
Subject: Re: Sieve of Eratosthenes Performance: various languages (Re: [Caml-list] productivity improvement)
Message-ID: <20020710204859.GC18091@fichte.ai.univie.ac.at>
Mail-Followup-To: Oleg <oleg_inconnu@myrealbox.com>,
	sebastien FURIC <sebastien.furic@tni-valiosys.com>,
	Shannon --jj Behrens <jjinux@yahoo.com>, caml-list@inria.fr
References: <20020709182022.69599.qmail@web10706.mail.yahoo.com> <3D2C063E.25EA1D8D@tni.fr> <200207102014.QAA14544@dewberry.cc.columbia.edu>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <200207102014.QAA14544@dewberry.cc.columbia.edu>
User-Agent: Mutt/1.4i
Organization: Austrian Research Institute for Artificial Intelligence
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk

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