This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

[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: 2002-07-10 (20:49) From: Markus Mottl 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

```