Confusing performance results for prime

[Patrick Ellis]

"Greg Brunet" <gregbrunet at NOSPAMsempersoft.com> wrote in message
news:vp3liuqs76bd5a at corp.supernews.com...
> Thanks for the responses!  After some more testing based on the
> responses I got, here's some additional notes:
>
> <snipped the notes>

Here are some functions from an earlier discusion. Note that 1 and 2
are faster, but more memory intensive. They create a list (or array)
of all odd numbers and weed out the non-primes. 3 and 1ix only
create the primes, saving a lot of space.

==================================================

from __future__ import generators
import Numeric
import math
import sys
import time

# Basically, Tim Peter's version of sieve.
def sieve1(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: break
        # 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
    primes[0] = 2
    return filter(None, primes)

# The same as sieve1, but modified by me to use numeric for more speed.
def sieve2(n):
    if n < 2:
        return []
    primes = Numeric.arrayrange(1, n+1, 2)
    limit = (int(math.sqrt(n)) / 2) + 1
    for p in primes[1:limit]:
        if p:
            # note that p*p is odd, so no need to subtract 1
            # before shifting right -- same thing in the end
            primes[(p*p)>>1::p] = 0
    return list(Numeric.nonzero(primes))

# Not sure where this came from, but I am sure I didn't write it. This is
# a generator, the function is below.
def sieve3gen(maximum):
    "Generate all primes <= maximum."
    if maximum >= 2:
        yield 2
    if maximum >= 3:
        yield 3
    # candidate takes on all integer values > 3 that aren't divisible by
    # 2 or 3.
    candidate = 5
    delta = 2  # flips between 2 and 4
    # Map i to (d, 6*p), where d is 2*p or 4*p, p is a prime dividing i,
    # and i+d is the next multiple of p larger than i not divisible by
    # 2 or 3.  As the algorithm proceeds, f will contain one entry for
    # each prime <= sqrt(maximum) discovered so far (excepting 2 and 3).
    f = {}
    fetch = f.pop
    adding = candidate**2 <= maximum
    while candidate <= maximum:
        if candidate in f:
            d, s = fetch(candidate)
            # candidate + d is next multiple of s/6 that isn't divisible
            # by 2 or 3
            i = candidate + d
            d = s-d
            while i in f:
                i += d
                d = s-d
            f[i] = d, s
        else:
            yield candidate
            if adding:
                sq = candidate**2
                f[sq] = delta * candidate, 6 * candidate
                adding = sq <= maximum
        candidate += delta
        delta = 6 - delta

# Convert the generator into a function that matches the others.
def sieve3(n):
    return [i for i in sieve3gen(n)]

# One of the algorithms from this thread, for comparison.
# test using list of primes - w/ int typecast and xrange
# (to see if xrange is faster - no noticable difference)
def Primes1ix(y):
    primes = [3]
    for p in xrange(5, y, 2):
        limit = int(math.sqrt(p))
        for factor in primes:
            if factor > limit:      # then number is prime
                primes.append(p)
                break
            elif p % factor == 0:   # then it's *not* prime
                break
    return [2] + primes


if __name__ == "__main__":
    n=1000000
    if len(sys.argv) > 1:
        n = int(sys.argv[1])

    times = []
    primes = []
    for pfun in (sieve1, sieve2, sieve3, Primes1ix):
        tb = time.time()
        p = pfun(n)
        primes.append(len(p))
        dt = time.time() - tb
        times.append(dt)
    fastest = min(times)

    print 'Prime number algorithms/optimizations - up to:', n
    if (fastest==0):
        print '*** Percentages are invalid (fastest time is 0) ***'
        fastest = .01
    for i, pfun in enumerate((sieve1, sieve2, sieve3, Primes1ix)):
        print '%s: %s primes up to %s in %5.3f secs (+%3.1f%%)' % (
            pfun.__name__, primes[i], n, times[i],
            (times[i]-fastest)*100/fastest)

===================================================

Prime number algorithms/optimizations - up to: 1000000
sieve1: 78498 primes up to 1000000 in 0.593 secs (+99.7%)
sieve2: 78498 primes up to 1000000 in 0.297 secs (+0.0%)
sieve3: 78498 primes up to 1000000 in 1.078 secs (+263.0%)
Primes1ix: 78498 primes up to 1000000 in 10.438 secs (+3414.5%)