good chemistry is complicated,and a little bit messy -LW PerlMonks

### 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,{
@_=(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:
RoutineNIterationsTime
Ase10001002
Maverick10001002
Ase1000010021
Maverick1000010024
Ase100000100221
Maverick100000100236

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.
-ase

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...

/\/\averick

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.
-ase

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

Create A New User
Node Status?
node history
Node Type: note [id://20730]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (3)
As of 2021-05-15 03:18 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Perl 7 will be out ...

Results (150 votes). Check out past polls.

Notices?