Fast Prime List Functions

vegaseat 3 Tallied Votes 392 Views Share

There is always room for optimizing primelist functions. Here is an assortment timed with Python module timeit ...

TrustyTony commented: Good to collect some quality ways to summarize the zillion threads here in Daniweb. These are also kinds which newbies can not claim their own ;-) +12
'''primelist_timing1.py
timing some very fast primelist functions
tested with Python27 and Python32  by  vegaseat
'''

import timeit
import numpy
import sys

print("Python version:\n %s\n" % sys.version)

def time_function(stmt, setup):
    """
    use module timeit to time functions
    """
    # to enable garbage collection start setup with 'gc.enable();'
    #setup = 'gc.enable();' + setup
    t = timeit.Timer(stmt, setup)
    times = 10000
    num = 100
    # times*num has to be 1000000 to get time in microseconds/pass
    # (lower num is a little less precise but saves time)
    elapsed = (times * t.timeit(number=num))
    print("%-20s --> %0.2f microseconds/pass" % (stmt, elapsed))

def primelist_bw(n):
    """
    returns  a list of primes < n
    by Bill Woods
    """
    sieve = [True] * (n>>1)
    for x in range(3, int(n**0.5)+1, 2):
        if sieve[x>>1]:
            sieve[x*x//2::x] = [False] * ((n-x*x-1)//(x<<1)+1)
    return [2] + [(x<<1)+1 for x in range(1, n>>1) if sieve[x]]


def primelist_ds(n):
    """
    returns  a list of primes < n
    """
    sieve = [True] * (n>>1)
    for x in range(3, int(n**0.5)+1, 2):
        if sieve[x>>1]:
            sieve[(x*x)>>1::x] = [False] * ((n-x*x-1)//(x<<1)+1)
    return [2] + [(x<<1)+1 for x in range(1, n>>1) if sieve[x]]

def primes_numpy(n):
    """
    requires module numpy and n>=6,
    returns a list of primes 2 <= p < n
    """
    sieve = numpy.ones(n//3 + (n%6==2), dtype=numpy.bool)
    sieve[0] = False
    for x in range(int(n**0.5)//3+1):
        if sieve[x]:
            k = 3*x + 1|1
            sieve[((k*k)//3)::2*k] = False
            sieve[(k*k+4*k-2*k*(x&1))//3::2*k] = False
    return numpy.r_[2,3,((3*numpy.nonzero(sieve)[0]+1)|1)].tolist()

# time a function
stmt = 'primelist_bw(1000000)'
setup = 'from __main__ import primelist_bw'
time_function(stmt, setup)

# time a function
stmt = 'primelist_ds(1000000)'
setup = 'from __main__ import primelist_ds'
time_function(stmt, setup)

# time a function
stmt = 'primes_numpy(1000000)'
setup = 'from __main__ import primes_numpy, numpy'
time_function(stmt, setup)

print('-'*60)

# additional test (show the last 5 primes) ...
print(primelist_bw(1000000)[-5:])
print(primelist_ds(1000000)[-5:])
print(primes_numpy(1000000)[-5:])

'''result ...
Python version:
 2.7.3 (default, Apr 10 2012, 23:31:26) [MSC v.1500 32 bit (Intel)]

primelist_bw(1000000) --> 75969.22 microseconds/pass
primelist_ds(1000000) --> 73669.90 microseconds/pass
primes_numpy(1000000) --> 9016.74 microseconds/pass
------------------------------------------------------------
[999953, 999959, 999961, 999979, 999983]
[999953, 999959, 999961, 999979, 999983]
[999953, 999959, 999961, 999979, 999983]


Python version:
 3.2.3 (default, Apr 11 2012, 07:15:24) [MSC v.1500 32 bit (Intel)]

primelist_bw(1000000) --> 77284.28 microseconds/pass
primelist_ds(1000000) --> 75547.38 microseconds/pass
primes_numpy(1000000) --> 28055.11 microseconds/pass
------------------------------------------------------------
[999953, 999959, 999961, 999979, 999983]
[999953, 999959, 999961, 999979, 999983]
[999953, 999959, 999961, 999979, 999983]
'''
vegaseat 1,735 DaniWeb's Hypocrite Team Colleague

I used the above primelist code for benchmarking and got these results:

'''result (on a Toshiba Satellite P875 with an Intel Core i5 processor) ...

Python version:
 2.7.3 (default, Apr 10 2012, 23:31:26) [MSC v.1500 32 bit (Intel)]

primelist_bw(1000000) --> 39992.52 microseconds/pass
primelist_ds(1000000) --> 37842.45 microseconds/pass
primes_numpy(1000000) --> 7044.22 microseconds/pass
------------------------------------------------------------
[999953, 999959, 999961, 999979, 999983]
[999953, 999959, 999961, 999979, 999983]
[999953, 999959, 999961, 999979, 999983]


Python version:
 3.2.1 (default, Jul 10 2011, 21:51:15) [MSC v.1500 32 bit (Intel)]

primelist_bw(1000000) --> 54640.40 microseconds/pass
primelist_ds(1000000) --> 54041.90 microseconds/pass
primes_numpy(1000000) --> 8586.35 microseconds/pass
------------------------------------------------------------
[999953, 999959, 999961, 999979, 999983]
[999953, 999959, 999961, 999979, 999983]
[999953, 999959, 999961, 999979, 999983]


Python version:
 3.3.0 (v3.3.0:bd8afb90ebf2, Sep 29 2012, 10:55:48) [MSC v.1600 32 bit (Intel)]

primelist_bw(1000000) --> 64008.36 microseconds/pass
primelist_ds(1000000) --> 64330.56 microseconds/pass
primes_numpy(1000000) --> 8462.06 microseconds/pass
------------------------------------------------------------
[999953, 999959, 999961, 999979, 999983]
[999953, 999959, 999961, 999979, 999983]
[999953, 999959, 999961, 999979, 999983]
'''
TrustyTony 888 pyMod Team Colleague Featured Poster

Hmmm... regression for version 3.3.0, except numpy and Python2 edge does not seem to go away. Lets try shedskin also, it has not multiprecission though. Actually maybe the reason for disadvantage of Python3 is because there is not short integer type?

rubik-pypol 0 Newbie Poster

Nice one! Probably on Python 2 you can slightly optimize by using xrange instead of range.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.