Velocity Reviews > Remarkable results with psyco and sieve of Eratosthenes

# Remarkable results with psyco and sieve of Eratosthenes

Gabriel Genellina
Guest
Posts: n/a

 11-30-2006
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

George Sakkis
Guest
Posts: n/a

 11-30-2006
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

bearophileHUGS@lycos.com
Guest
Posts: n/a

 11-30-2006
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

Pekka Karjalainen
Guest
Posts: n/a

 11-30-2006
In article <(E-Mail Removed) .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

Klaus Alexander Seistrup
Guest
Posts: n/a

 11-30-2006
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/

Klaas
Guest
Posts: n/a

 11-30-2006
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