Entry

List size hints

Jul 5th, 2000 09:59
Nathan Wallace, unknown unknown, Hans Nowak, Snippet 45, Tim Peters

"""
Packages: maths.sieves;basic_datatypes.lists
"""

"""
[Gordon McMillan, playing bookmaker for a prime-sieve battle]
> The gauntlet has been thrown!
>
> I've got Tim at 5:4, (but only because Christian has a family to
> support).
>
> Any takers?

Well, as I wrote, "I'll attach a simple sieve" -- speed was not its goal.  I
actually obtained it by *un*optimizing the sieve I use (much like Chris &
Mike's later nightmares; see attached) so that it used list.append again,
and didn't require poor James to reverse-engineer an irrelevant (for his
purposes) index<->number mapping.  OTOH, no sieve without *some* "square it"
trickery is worth posting no matter what the purpose <snort>.

Notes:

+ The speed of the attached is indistinguishable (on my platform) from
Mike's mcfsieve3.

+ OTOH, unlike mcfsieve3 or tahsieve1 or tissieve2 it gets the right answer
when passed 25 <wink>.

+ Christian and I implicitly rely on sqrt returning the exact answer when
it's representable, while Mike and TimH rely on n ** 0.5 doing that.
IEEE-754 guarantees the former but not the latter.  We're all gambling,
though, for portable code.

+ The attached doesn't need to "insert 2" at the end.  But that goes so fast
it's hardly worth avoiding.

+ Agree with Chris that you can't nuke the multiples of 3 too without
slowing it down, simply due to the boost in the # of trips around Python's
eval loop; agree too that it can pay in a compiled language.

+ I don't know a faster method, but have heard such exist <challenging
wink>.  In Real Life, it can pay to "bunch up" a number of primes before
doing the cross-out business, then cross out multiple multiples in adjacent
blocks whose size is determined by platform cache characteristics.  But,
again, the code to manage that incurs too much overhead in Python -- besides
which, it's insane.

professional-courtesy-to-leave-*something*-for-fortran-ly y'rs  - tim
"""

import math

def sieve(n):
    if n < 2:
        return []
    limit = int(math.sqrt(n))
    primes = range(1, n+1, 2)
    primes[0] = 0
    n = len(primes)
    for p in primes:
        if not p: continue
        if p <= limit:
            # note that p*p is odd, so no need to subtract 1
            # before shifting right -- same thing in the end
            for i in xrange((p*p)>>1, n, p):
                primes[i] = 0
            continue
        break
    primes[0] = 2
    return filter(None, primes)