[Shootout-list] C++ sieve using vector<bool>

[Isaac Gouy]

FAQ http://shootout.alioth.debian.org/faq.php?sort=fullcpu#contribute


--- Jon Harrop <jon@ffconsultancy.com> wrote:
> 
> I saw a discussion where someone said it would be nice to have a C++ 
> implementation of the sieve (sieve-bits?) which used vector<bool>.
> Indeed, 
> this is the obvious way to implement the sieve in C++. I happen to
> have one 
> lying around:
> 
> #include <vector>
> 
> int sieve(int n) {
>   std::vector<bool> t(n+1);
>   int count = 0;
> 
>   for (int i=2; i<=n; ++i)
>     if (! t.at(i)) {
>       ++count;
>       for (int j=i*2; j<=n; j+=i) t.at(j) = true;
>     }
> 
>   return count;
> }
> 
> Hopefully that'll be of some use. :-)
> 
> IMHO, this counts as the C++ implementation of both nsieve and
> nsieve-bits as 
> the STL's vector implements arrays and happens to be partially
> specialised 
> for bools. Note that this implementation uses bounds checking.
> 
> Also, performance can be improved significantly by reading from the
> underlying 
> array and only writing if the write will change the contents. I
> believe this 
> is because the write-cache doesn't fill as much. This OCaml
> implementation is 
> faster than the one currently on the shootout on my computer (but
> maybe it 
> isn't "legal"):
> 
> open Bigarray
> 
> let nsieve n =
>   let a =  Array1.create int8_unsigned c_layout ((n lsr 3) + 2) in
>   Array1.fill a 0xFF;
>   let rec clear i j =
>     if j <= n then (
>       let ic = j lsr 3 in
>       let bit = a.{ic} land lnot(1 lsl (j land 0x7)) in
>       if a.{ic} <> bit then a.{ic} <- bit;
>       clear i (j + i) ) in
>   let count = ref 0 in
>   for i = 2 to n do
>     if a.{i lsr 3} land (1 lsl (i land 0x7)) > 0 then begin
>       incr count;
>       if i*i <= n then clear i (2*i)
>     end
>   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(Array.get Sys.argv 1)
>     with _ -> (Printf.printf "usage: %s N\n" Sys.argv.(0); exit 2) in
>   test n;
>   if n >= 1 then test(n-1);
>   if n >= 2 then test(n-2)
> 
> -- 
> Dr Jon D Harrop, Flying Frog Consultancy Ltd.
> Objective CAML for Scientists
> http://www.ffconsultancy.com/products/ocaml_for_scientists
> 
> _______________________________________________
> Shootout-list mailing list
> Shootout-list@lists.alioth.debian.org
> http://lists.alioth.debian.org/mailman/listinfo/shootout-list
> 

__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com