Entry

Speedy sieves

Jul 5th, 2000 09:59
Nathan Wallace, unknown unknown, Hans Nowak, Snippet 33, Mike Fletcher

"""
Packages: maths.sieves
"""

"""
Oh, goody, speed tests again!

1)  if not p: continue  is fairly expensive compared to if p: dosomething
2) roll the (q-3)/2 into the xrange parameters and you should save some
processing power
3) not sure about the adding lists versus inserting, didn't seem to hurt
4) results seem to be identical

Enjoy yourselves,
Mike
"""

def tissieve(n):
	candidates = range(3, n+1, 2)
	for p in candidates:
		if not p: continue
		for q in xrange(3*p, n+1, 2*p):
			candidates[(q-3)/2] = 0
	return [2] + filter(None, candidates)

def mcfsieve1( n):
	candidates = range(3, n+1, 2)
	for p in candidates:
		if p:
			for q in xrange(3*p, n+1, 2*p):
				candidates[(q-3)/2] = 0
	candidates.insert( 0, 2) # save extra copy maybe?
	return filter(None, candidates)
def mcfsieve2( n):
	candidates = range(3, n+1, 2)
	for p in candidates:
		if p:
			for q in xrange( ((3*p)-3)/2, (n-2)/2, p):
				candidates[ q] = 0
	candidates.insert( 0, 2) # save extra copy maybe?
	return filter(None, candidates)

def test():
	import time
	a = time.time()
	tissieve( 10**6)
	b = time.time()
	print 'tissieve: ', b-a
	a = time.time()
	mcfsieve1( 10**6)
	b = time.time()
	print 'mcfsieve1: ', b-a
	a = time.time()
	mcfsieve2( 10**6)
	b = time.time()
	print 'mcfsieve2: ', b-a

def test2():
	a = tissieve( 10**6) 
	b = mcfsieve1( 10**6) 
	c = mcfsieve2( 10**6)
	print 'Are same?', a == b, b == c	
	

if __name__ == '__main__':
	test()
	test2()