Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical

RE: sieve of Eratosthenes

by ase (Monk)
on Jul 01, 2000 at 11:49 UTC ( #20730=note: print w/replies, xml ) Need Help??

in reply to sieve of erothenes

This has been an interesting thread to follow. I played around with a Bit Vector algorithm... going for efficiency at the cost of a little brevity. Here's what I came up with:
#!usr/bin/perl -w use Benchmark; timethese(100,{ Adam => sub { @_=(1); L:for(2..1000) { $i=-@_; #updated per node 20757 7/13/2000 while(++$i){ #ditto next L if!($_%$_[$i]) } push@_,$_ } #print join "\t", @_; }, Maverick => sub { for(1..1000){ push@_,$_; for(@_[1..$#_-1]){ pop@_&&last if!($_[-1] %$_) } } #print join "\t", @_; }, Ase => sub { $v='1' x 1000; for(2..1000){ next if !vec($v,$_-1,8); for($q=$_*2;$q<1001;$q+=$_){ vec($v,$q-1,8)=0 } } #print join "\t",grep {vec($v,$_-1,8)} (1..1000); }, });

Here's a table summarizing the data:
Benchmark is your friend!

It seems Mavericks code is only very slightly slower with the benefit of being slightly shorter.

This was done on a 300 mHz amd K6 running win 98 and perl 5.005_02 (activestate 509) as always your mileage may vary.

Update 7/13/2000: I modified Adam's code per this node and re-benchmarked accordingly.

Replies are listed 'Best First'.
RE: RE: sieve of Eratosthenes
by maverick (Curate) on Jul 01, 2000 at 17:43 UTC
    Nice algorithm! The idea of using vectors never occured to me.

    I went back and uncomment the print statements to see what kind of overhead the grep might cause. At N=100000 I end up with:

    Benchmark: timing 100 iterations of Ase, Maverick... Ase: 142 wallclock secs (141.93 usr + 0.04 sys = 141.97 CPU) Maverick: 166 wallclock secs (166.05 usr + 0.00 sys = 166.05 CPU)
    I would have expected us to end up with closer times, but your's ends up being 24 seconds faster? wow. So, I removed the prints and got:
    Benchmark: timing 100 iterations of Ase, Maverick... Ase: 122 wallclock secs (121.11 usr + 0.00 sys = 121.11 CPU) Maverick: 164 wallclock secs (164.65 usr + 0.03 sys = 164.68 CPU)
    I'm running this on a PII 400, using Red Hat Linux and the stock perl RPM (5.005_03). It would seem that vec is much faster under Linux than under windows.

    Hmmm...I wonder how these benchmark out on other platforms...


      I wish I could claim the algorithm for my own, but I can't.. Ironically enough, I got it from "More Programming Pearls" by Jon Bentley (nothing to do with perl as its copyright date is 1988) He deals mostly with awk but I highly recommend it as well as its out of print predecessor "Programming Pearls"... which I was able to obtain a while ago.... good stuff for any programmer.

      I would also be interested in benchmarks on other platforms.

Re: RE: sieve of Eratosthenes
by cforde (Monk) on May 19, 2001 at 04:23 UTC
    In the pursuit of efficiency I have come up with a slightly different implementation: Carl1. In Carl2 I tried to optimize at the expense of a few more characters.

    On my WinNT PIII 800Mhz machine with ActiveState 522 both of these are faster than ase's Bit Vector implementation.

    Carl1: @p=(1);for(2..10000){if(!$n[$_]){push@p,$_;for($k=$_*$_;$k<=10000; +$n[$k]=1,$k+=$_){}}} Carl2: @p=(1,2);for($_=3;$_<=10000;$_+=2){if(!$n[$_]){push@p,$_;for($k=$_ +*$_;$k<=10000;$n[$k]=1,$k+=$_){}}}
    One thing that I found interesting is that for n less than about 10,000, Carl1 is significantly faster than Carl2. The loop control overhead must be pretty significant.

    Have fun,
    Carl Forde

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://20730]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (3)
As of 2017-08-20 01:31 GMT
Find Nodes?
    Voting Booth?
    Who is your favorite scientist and why?

    Results (313 votes). Check out past polls.