- **Python**
(*http://www.velocityreviews.com/forums/f43-python.html*)

- - **Remarkable results with psyco and sieve of Eratosthenes**
(*http://www.velocityreviews.com/forums/t396840-remarkable-results-with-psyco-and-sieve-of-eratosthenes.html*)

Remarkable results with psyco and sieve of EratosthenesJust 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=[3] 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() |

Re: Remarkable results with psyco and sieve of Eratosthenes> #!/usr/bin/python -OO > import math > import sys > import psyco > > psyco.full() > > def primes(): > primes=[3] > 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=[3] 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 |

Re: Remarkable results with psyco and sieve of EratosthenesSteve 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 |

Re: Remarkable results with psyco and sieve of EratosthenesWill 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 . |

Re: Remarkable results with psyco and sieve of EratosthenesBeliavsky 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 |

Re: Remarkable results with psyco and sieve of Eratosthenes> 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] = [0] * -((bottom-top)//si) return [2]+filter(None, sieve) smallPrimes(10**7) > > ============ > > #!/usr/bin/python -OO > import math > import sys > import psyco > > psyco.full() > > def primes(): > primes=[3] > 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() |

Re: Remarkable results with psyco and sieve of EratosthenesWill 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? |

Re: Remarkable results with psyco and sieve of Eratosthenesdickinsm@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... |

Re: Remarkable results with psyco and sieve of EratosthenesOn Nov 29, 6:59 pm, "Steve Bergman" <s...@rueb.com> wrote: > dicki...@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. Right. I guess the point of the sieve is that you don't have to spend any time finding that a given odd integer is not divisible by a given prime; all the multiplies are done up front, so you save all the operations corresponding to the case when x % y != 0 in your code. Or something. > Anyway, this is indeed fast as long as you have enough memory to handle > it for the range supplied. The sieve can be segmented, so that the intermediate space requirement for computing the primes up to n is O(sqrt(n)). (Of course you'll still need O(n/log n) space to store the eventual list of primes.) Then there are all sorts of bells and whistles (not to mention wheels) that you can add to improve the running time, most of which would considerably complicate the code. The book by Crandall and Pomerance (Primes: A Computational Perspective) goes into plenty of detail on all of this. Mark Dickinson |

Re: Remarkable results with psyco and sieve of EratosthenesOn 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. |

All times are GMT. The time now is 09:50 AM. |

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.

SEO by vBSEO ©2010, Crawlability, Inc.