435,491 Members | 3,273 Online + Ask a Question
Need help? Post your question and get tips & solutions from a community of 435,491 IT Pros & Developers. It's quick & easy.

Remarkable results with psyco and sieve of Eratosthenes

 P: n/a Just wanted to report a delightful little surprise while experimenting with psyco. The program below performs astonoshingly well with psyco. It finds all the prime numbers < 10,000,000 Processor is AMD64 4000+ running 32 bit. Non psyco'd python version takes 94 seconds. psyco'd version takes 9.6 seconds. But here is the kicker. The very same algorithm written up in C and compiled with gcc -O3, takes 4.5 seconds. Python is runng half as fast as optimized C in this test! Made my day, and I wanted to share my discovery. BTW, can this code be made any more efficient? ============ #!/usr/bin/python -OO import math import sys import psyco psyco.full() def primes(): primes= for x in xrange(5,10000000,2): maxfact = int(math.sqrt(x)) flag=True for y in primes: if y maxfact: break if x%y == 0: flag=False break if flag == True: primes.append(x) primes() Nov 29 '06 #1
15 Replies

 P: n/a #!/usr/bin/python -OO import math import sys import psyco psyco.full() def primes(): primes= for x in xrange(5,10000000,2): maxfact = int(math.sqrt(x)) flag=True for y in primes: if y maxfact: break if x%y == 0: flag=False break if flag == True: primes.append(x) primes() Some trivial optimizations. Give this a whirl. def primes(): sqrt=math.sqrt primes= for x in xrange(5,10000000,2): maxfact = int(sqrt(x)) for y in primes: if y maxfact: primes.append(x) break if not x%y: break return primes -- blog: http://www.willmcgugan.com Nov 29 '06 #2

 P: n/a Steve Bergman wrote: Just wanted to report a delightful little surprise while experimenting with psyco. The program below performs astonoshingly well with psyco. It finds all the prime numbers < 10,000,000 Actualy, it doesn't. You forgot 1 and 2. Will McGugan -- blog: http://www.willmcgugan.com Nov 29 '06 #3

 P: n/a Will McGugan wrote: Steve Bergman wrote: Just wanted to report a delightful little surprise while experimenting with psyco. The program below performs astonoshingly well with psyco. It finds all the prime numbers < 10,000,000 Actualy, it doesn't. You forgot 1 and 2. The number 1 is not generally considered to be a prime number -- see http://mathworld.wolfram.com/PrimeNumber.html . Nov 29 '06 #4

 P: n/a Beliavsky wrote: > The number 1 is not generally considered to be a prime number -- see http://mathworld.wolfram.com/PrimeNumber.html . I stand corrected. -- blog: http://www.willmcgugan.com Nov 29 '06 #5

 P: n/a BTW, can this code be made any more efficient? I'm not sure, but the following code takes around 6 seconds on my 1.2Ghz iBook. How does it run on your machine? def smallPrimes(n): """Given an integer n, compute a list of the primes < n""" if n <= 2: return [] sieve = range(3, n, 2) top = len(sieve) for si in sieve: if si: bottom = (si*si - 3)//2 if bottom >= top: break sieve[bottom::si] =  * -((bottom-top)//si) return +filter(None, sieve) smallPrimes(10**7) > ============ #!/usr/bin/python -OO import math import sys import psyco psyco.full() def primes(): primes= for x in xrange(5,10000000,2): maxfact = int(math.sqrt(x)) flag=True for y in primes: if y maxfact: break if x%y == 0: flag=False break if flag == True: primes.append(x) primes() Nov 29 '06 #6

 P: n/a Will McGugan wrote: Some trivial optimizations. Give this a whirl. I retimed and got 9.7 average for 3 runs on my version. Yours got it down to 9.2. 5% improvement. Not bad. (Inserting '2' at the beginning doesn't seem to impact performance much.;-) ) BTW, strictly speaking, shouldn't I be adding something to the floating point sqrt result, before converting to int, to allow for rounding error? If it is supposed to be 367 but comes in at 366.99999999, don't I potentially classify a composite as a prime? How much needs to be added? Nov 29 '06 #7

 P: n/a di******@gmail.com wrote: BTW, can this code be made any more efficient? I'm not sure, but the following code takes around 6 seconds on my 1.2Ghz iBook. How does it run on your machine? Hmm. Come to think of it, my algorithm isn't the sieve. Anyway, this is indeed fast as long as you have enough memory to handle it for the range supplied. It comes in at 1.185 seconds average on this box. Come to think of it, there is a supposedly highly optimized version of the sieve in The Python Cookbook that I've never bothered to actually try out. Hmmm... Nov 29 '06 #8

 P: n/a On Nov 29, 6:59 pm, "Steve Bergman"

 P: n/a On Wed, 29 Nov 2006 15:35:39 -0800, Steve Bergman wrote: BTW, strictly speaking, shouldn't I be adding something to the floating point sqrt result, before converting to int, to allow for rounding error? If you don't mind doing no more than one unnecessary test per candidate, you can just add one to maxfact to allow for that. Or use round() rather than int(). Or don't convert it at all, just say: maxfact = math.sqrt(x) and compare directly to that. If it is supposed to be 367 but comes in at 366.99999999, don't I potentially classify a composite as a prime? Do you fear the math.sqrt() function is buggy? If so, all bets are off :-) How much needs to be added? No more than 1, and even that might lead you to sometimes performing an unnecessary test. -- Steven. Nov 30 '06 #10

 P: n/a At Wednesday 29/11/2006 20:35, Steve Bergman wrote: >BTW, strictly speaking, shouldn't I be adding something to the floatingpoint sqrt result, before converting to int, to allow for roundingerror? If it is supposed to be 367 but comes in at 366.99999999, don'tI potentially classify a composite as a prime? You could avoid sqrt using divmod (which gets the % result too); stop when quotient<=divisor. But this approach creates a tuple and then unpacks it, so you should time it to see if there is an actual speed improvement. -- Gabriel Genellina Softlab SRL __________________________________________________ Correo Yahoo! Espacio para todos tus mensajes, antivirus y antispam ¡gratis! ¡Abrí tu cuenta ya! - http://correo.yahoo.com.ar Nov 30 '06 #11

 P: n/a Will McGugan wrote: #!/usr/bin/python -OO import math import sys import psyco psyco.full() def primes(): primes= for x in xrange(5,10000000,2): maxfact = int(math.sqrt(x)) flag=True for y in primes: if y maxfact: break if x%y == 0: flag=False break if flag == True: primes.append(x) primes() Some trivial optimizations. Give this a whirl. def primes(): sqrt=math.sqrt primes= for x in xrange(5,10000000,2): maxfact = int(sqrt(x)) for y in primes: if y maxfact: primes.append(x) break if not x%y: break return primes You can also save an attribute lookup for append; just add append = primes.append outside of the loop and replace primes.append(x) with append(x) That should cut down a few fractions of second. George Nov 30 '06 #12

 P: n/a George Sakkis: You can also save an attribute lookup for append; just add append = primes.append outside of the loop and replace primes.append(x) with append(x) That should cut down a few fractions of second. We were talking about Psyco, and I think with Psyco (just released for Py 2.5, BTW) such tricks are less useful. Bye, bearophile Nov 30 '06 #13

 P: n/a In article <11**********************@h54g2000cwb.googlegroups .com>, Steve Bergman wrote: >BTW, can this code be made any more efficient? >def primes(): primes= for x in xrange(5,10000000,2): maxfact = int(math.sqrt(x)) flag=True for y in primes: if y maxfact: break [...] You can omit the call to math.sqrt if you test this instead. y*y x in place of if y maxfact: . Pka Nov 30 '06 #14

 P: n/a Pekka Karjalainen wrote: You can omit the call to math.sqrt if you test this instead. y*y x in place of if y maxfact: . Or use sqrt = lambda x: x ** .5 Cheers, -- Klaus Alexander Seistrup http://klaus.seistrup.dk/ Nov 30 '06 #15

 P: n/a Klaus Alexander Seistrup wrote: Pekka Karjalainen wrote: You can omit the call to math.sqrt if you test this instead. y*y x in place of if y maxfact: . Or use sqrt = lambda x: x ** .5 Test it: \$ python -m timeit -s "from math import sqrt" "sqrt(5.6)" 1000000 loops, best of 3: 0.445 usec per loop \$ python -m timeit -s "sqrt = lambda x: x**.5" "sqrt(5.6)" 1000000 loops, best of 3: 0.782 usec per loop Note that this overhead is almost entirely in function calls; calling an empty lambda is more expensive than a c-level sqrt: \$ python -m timeit -s "sqrt = lambda x: x" "sqrt(5.6)" 1000000 loops, best of 3: 0.601 usec per loop Just math ops: \$ python -m timeit -s "x = 5.6" "x*x" 10000000 loops, best of 3: 0.215 usec per loop \$ python -m timeit -s "x = 5.6" "x**.5" 1000000 loops, best of 3: 0.438 usec per loop Of course, who knows that psyco does with this under the hood. -Mike Nov 30 '06 #16

This discussion thread is closed

Replies have been disabled for this discussion. 