[Shootout-list] nsieve-bits (OCaml)

[Christophe TROESTLER]

Hi,

Here is a new version of nsieve-bits for OCaml.  I hope you will find
it more readable.  On my machine (P4 2.40GHz, Debian testing), it is
also faster than the previous OCaml version and even faster than gcc
for inputs = 10, 11, 12.  (For n = 13, the gcc version segfault while
the OCaml program runs fine.  I believe this is also interesting
information.)

I'd also like to point out that several implementations have a
mistake.  For example the C version declares

        bits a[m / NBITS];

but what e.g. if m < NBITS ?  The are no problems for the tests
performed because "m" is always a multiple of 8...

Best regards,
ChriS
-------------- next part --------------
open Bigarray

let nsieve m =
  let a =  Array1.create int8_unsigned c_layout ((m lsr 3) + 1) in
  Array1.fill a 0xFF;
  let rec clear i j =
    if j < m then (
      let ic = j lsr 3 in
      a.{ic} <- a.{ic} land lnot(1 lsl (j land 0x7));
      clear i (j + i)
    ) in
  let count = ref 0 in
  for i = 2 to m - 1 do
    if a.{i lsr 3} land (1 lsl (i land 0x7)) > 0 then
      (clear i (i+i); incr count)
  done;
  !count


let test n =
  let m = (1 lsl n) * 10000 in
  Printf.printf "Primes up to %8i %8i\n" m (nsieve m)

let () =
  let n =
    try int_of_string Sys.argv.(1)
    with _ -> (Printf.printf "usage: %s N" Sys.argv.(0); exit 2) in
  test n;
  if n >= 1 then test(n-1);
  if n >= 2 then test(n-2)