Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??
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:
RoutineNIterationsTime
Adam10001005
Ase10001002
Maverick10001002
Adam10000100203
Ase1000010021
Maverick1000010024
Ase100000100221
Maverick100000100236
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.
-ase


In reply to RE: sieve of Eratosthenes by ase
in thread sieve of erothenes by maverick

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others cooling their heels in the Monastery: (10)
    As of 2014-07-14 09:12 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      When choosing user names for websites, I prefer to use:








      Results (257 votes), past polls