Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid
 
PerlMonks  

(tye)Re3: (Golf): Sieve of Eratosthenes

by tye (Cardinal)
on May 20, 2001 at 01:56 UTC ( #81769=note: print w/ replies, xml ) Need Help??


in reply to (tye)Re2: (Golf): Sieve of Eratosthenes
in thread (Golf): Sieve of Eratosthenes

tilly's comment about things being "nearly linear" threw me for a bit. Then I realized that the quadratic nature is countered by the outer loop only needing to run to sqrt(N) and the inner loop being somewhat similarly restricted.

Which made me realize that my solution was suboptimal. Here is a faster one at the same number of characters [ thanks to MeowChow noting that I'd stupidly left in a trailing semicolon in my previous one ;) ]:

sub sieve3 { grep{@_[map$a*$_,$_..@_/($a=$_)]=0if$_[$_]>1}@_=0..pop } # ^^ for( @ARGV ) { print "$_: ",join(" ",sieve3($_)),$/; }

In playing with this and verifying that I didn't break it, I noticed something interesting and expanded on it. For how long of a stretch can you go without hitting any prime numbers? Well, stopping at 0.5million (because of memory limits), here are the results. "xN" means there were N ties before a new "winner" appeared:

2=5-3(x2) # 3..5, 5..7 4=11-7(x3) # 7..11, 13..17, 19..23 6=29-23(x7) 8=97-89 14=127-113(x3) 18=541-523 20=907-887 22=1151-1129 34=1361-1327(x2) 36=9587-9551(x3) 44=15727-15683 52=19661-19609(x2) 72=31469-31397 86=156007-155921(x2) 96=360749-360653 112=370373-370261 114=492227-492113

        - tye (but my friends call me "Tye")


Comment on (tye)Re3: (Golf): Sieve of Eratosthenes
Select or Download Code
Re (tilly) 4: (Golf): Sieve of Eratosthenes
by tilly (Archbishop) on May 21, 2001 at 20:37 UTC
    In the Big-O analysis being able to stop the outer loop early turns out to be a red herring. Being able to stop the inner loop after 1/p operations is key, as is the density of the primes. It means that the work is O(n*(sum of 1/p)). The sum of 1/i scales like log(n), the density of the primes scales as 1/log(n), and between them they cancel out for O(n*log(log(n))).

    log(log(n)) is essentially constant in the range of numbers I can test before hitting memory limitations. Also there is a theoretical log(n) that we are missing from the overhead of addressing and representing ever larger numbers. While we tend to call that constant, in reality it is not.

    BTW if you are interested, longer tables of maximal gaps have been compiled...

Re: (tye)Re3: (Golf): Sieve of Eratosthenes
by tilly (Archbishop) on Feb 26, 2011 at 01:23 UTC
    And almost a decade later I was randomly looking at this, and realized that it could be made shorter still.
    sub sieve3 { grep{@_[map$a*$_,2..@_/($a=$_)]=0if$_[$_]>1}@_=0..pop }
    Never give up on that last optimization!

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://81769]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (19)
As of 2014-08-27 16:46 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (245 votes), past polls