Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

Re (tilly) 4: (Golf): Sieve of Eratosthenes

by tilly (Archbishop)
on May 21, 2001 at 20:37 UTC ( #82005=note: print w/ replies, xml ) Need Help??


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

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


Comment on Re (tilly) 4: (Golf): Sieve of Eratosthenes

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (7)
As of 2014-09-22 11:56 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (190 votes), past polls