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:
Here's a table summarizing the data:
Benchmark is your friend!
#!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:
Routine | N | Iterations | Time |
---|---|---|---|
Adam | 1000 | 100 | 5 |
Ase | 1000 | 100 | 2 |
Maverick | 1000 | 100 | 2 |
Adam | 10000 | 100 | 203 |
Ase | 10000 | 100 | 21 |
Maverick | 10000 | 100 | 24 |
Ase | 100000 | 100 | 221 |
Maverick | 100000 | 100 | 236 |
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 | |
by ase (Monk) on Jul 02, 2000 at 06:50 UTC | |
Re: RE: sieve of Eratosthenes
by cforde (Monk) on May 19, 2001 at 04:23 UTC |
In Section
Cool Uses for Perl