473,320 Members | 1,831 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

Remarkable results with psyco and sieve of Eratosthenes

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=[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()

Nov 29 '06 #1
15 1897
#!/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
Nov 29 '06 #2
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
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
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
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()
Nov 29 '06 #6

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

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


On Nov 29, 6:59 pm, "Steve Bergman" <s...@rueb.comwrote:
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

Nov 30 '06 #9
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
At Wednesday 29/11/2006 20:35, 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 it is supposed to be 367 but comes in at 366.99999999, don't
I 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
Will McGugan wrote:
#!/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
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
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
In article <11**********************@h54g2000cwb.googlegroups .com>,
Steve Bergman wrote:
>BTW, can this code be made any more efficient?
>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
[...]

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
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
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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

20
by: MSiegel | last post by:
hi there! i have to program the sieve of eratosthenes in php as a homework. after i had created an html file where the maximum is set i wrote a php script which doesn't work properly - actually...
0
by: Mark A. Washburn | last post by:
/* SIEVE OF ERATOSTHENES from BYTE magazine -------------------- -- compiled with jdk 1.1.7b with optimize on ( -O) -- Run times on 300 MHz Pentium 2 Windows 95 -- in order of output, from...
3
by: Dick Moores | last post by:
psyco is acting a bit psycho for me. Please see my spinForWeb.py at <http://www.rcblue.com/Python/spinForWeb.py> When psyco is in use, entering an integer somewhere between 2000 and 2500...
5
by: Fausto Arinos Barbuto | last post by:
Hi All; I have Psyco (on Windows XP) and now I want to install it on Linux, too. I FTP'd the tarball (tar.gz) from Psyco's site but can't get it compiled. First, I tried the usual "python...
6
by: Joe Piscapo | last post by:
Hello, When I compile my program in Visual Studio it does not work for every input, some numbers make it crash. But compiling in gcc works for those numbers that made it crash in Visual Studio. ...
6
by: danmcleran | last post by:
I'm not seeing much benefit from psyco (only 5-10% faster). Maybe this example is too trivial? Can someone give me some pointers as to what kind of code would see a dramatic benefit? Here's the...
4
by: knuxus | last post by:
Hey everyone.... I would appreciate any type of help if anyone could explain me how to translate this algorithm to Visual Basic, im still learning and i would appreciate this algorithm to my prime...
2
Blackout
by: Blackout | last post by:
Hi, I'm having problems with this C program. Whenever I run it, it doesn't print anything. The program is supposed to compute and display all the prime numbers from 1 - 300 using the sieve of...
3
by: jzakiya | last post by:
This is to announce the release of my paper "Ultimate Prime Sieve -- Sieve of Zakiiya (SoZ)" in which I show and explain the development of a class of Number Theory Sieves to generate prime...
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.