Python Optimization

[mukesh tiwari]

Hello everyone. I am new to python and previously i did programming in
c/c++.Could some one please help me to improve the run time for this
python program as i don't have idea how to optimized this code.This
code also seems to be more unpythonic so how to make it look like more
pythonic . I am trying for this problem(https://www.spoj.pl/problems/
FACT1/).
Thank you

# To change this template, choose Tools | Templates
# and open the template in the editor.

__author__="Mukesh Tiwari"
__date__ ="$Feb 10, 2010 1:35:26 AM$"


import random
from Queue import Queue


def gcd(a,b):
while b:
a,b=b,a%b
return a

def rabin_miller(p,t=1):
if(p<2):
return False
if(p!=2 and p%2==0):
return False
s=p-1
while(s%2==0):
s>>=1
for i in xrange(t):
a=random.randrange(p-1)+1
temp=s
mod=pow(a,temp,p)
while(temp!=p-1 and mod!=1 and mod!=p-1):
mod=(mod*mod)%p
temp=temp*2
if(mod!=p-1 and temp%2==0):
return False
return True
def brent(n):
if(n%2==0):
return 2;

x,c,m=random.randrange(0,n),random.randrange(1,n),random.randrange(1,n)
y,r,q=x,1,1
g,ys=0,0
while(True):
x=y
for i in range(r):
y,k=(y*y+c)%n,0
while(True):
ys=y
for i in range(min(m,r-k)):
y,q=(y*y+c)%n,q*abs(x-y)%n
g,k=gcd(q,n),k+m
if(k>= r or g>1):break
r=2*r
if(g>1):break
if(g==n):
while(True):
ys,g=(x*x+c)%n,gcd(abs(x-ys),n)
if(g>1):break
return g


def factor(n):
Q_1,Q_2=Queue(),[]
Q_1.put(n)
while(not Q_1.empty()):
l=Q_1.get()
if(rabin_miller(l)):
Q_2.append(l)
continue
d=brent(l)
if(d==l):Q_1.put(l)
else:
Q_1.put(d)
Q_1.put(l/d)
return Q_2



if __name__ == "__main__":
while(True):
n=int(raw_input())
if(n==0):break
L=factor(n)
L.sort()
#print L
i=0
s=""
while(i<len(L)):
cnt=L.count(L)
#print "%d^%d"%(L,cnt)
s+=str(L)+"^"+str(cnt)+" "
i+=cnt
print s[:-1]

 

[Mark Lawrence]

Hello everyone. I am new to python and previously i did programming in
c/c++.Could some one please help me to improve the run time for this
python program as i don't have idea how to optimized this code.This
code also seems to be more unpythonic so how to make it look like more
pythonic . I am trying for this problem(https://www.spoj.pl/problems/
FACT1/).
Thank you

# To change this template, choose Tools | Templates
# and open the template in the editor.

__author__="Mukesh Tiwari"
__date__ ="$Feb 10, 2010 1:35:26 AM$"


import random
from Queue import Queue


def gcd(a,b):
while b:
a,b=b,a%b
return a

def rabin_miller(p,t=1):
if(p<2):
return False
if(p!=2 and p%2==0):
return False
s=p-1
while(s%2==0):
s>>=1
for i in xrange(t):
a=random.randrange(p-1)+1
temp=s
mod=pow(a,temp,p)
while(temp!=p-1 and mod!=1 and mod!=p-1):
mod=(mod*mod)%p
temp=temp*2
if(mod!=p-1 and temp%2==0):
return False
return True
def brent(n):
if(n%2==0):
return 2;

x,c,m=random.randrange(0,n),random.randrange(1,n),random.randrange(1,n)
y,r,q=x,1,1
g,ys=0,0
while(True):
x=y
for i in range(r):
y,k=(y*y+c)%n,0
while(True):
ys=y
for i in range(min(m,r-k)):
y,q=(y*y+c)%n,q*abs(x-y)%n
g,k=gcd(q,n),k+m
if(k>= r or g>1):break
r=2*r
if(g>1):break
if(g==n):
while(True):
ys,g=(x*x+c)%n,gcd(abs(x-ys),n)
if(g>1):break
return g


def factor(n):
Q_1,Q_2=Queue(),[]
Q_1.put(n)
while(not Q_1.empty()):
l=Q_1.get()
if(rabin_miller(l)):
Q_2.append(l)
continue
d=brent(l)
if(d==l):Q_1.put(l)
else:
Q_1.put(d)
Q_1.put(l/d)
return Q_2



if __name__ == "__main__":
while(True):
n=int(raw_input())
if(n==0):break
L=factor(n)
L.sort()
#print L
i=0
s=""
while(i<len(L)):
cnt=L.count(L)
#print "%d^%d"%(L,cnt)
s+=str(L)+"^"+str(cnt)+" "
i+=cnt
print s[:-1]

A good starting point is
http://wiki.python.org/moin/PythonSpeed/PerformanceTips

HTH.

Mark Lawrence

 

[Mark Dickinson]

Hello everyone. I am new to python and previously i did programming in
c/c++.Could some one please help me to improve the run time for this
python program as i don't have idea how to optimized this code.
[...]

How much of a speedup do you need? Are we talking about orders of
magnitude (in which case you might want to consider using something
like the Multiple Polynomial Quadratic Sieve method instead, or as
well), or just a few percent?

(1) Have you profiled the code to see where it's spending most of its
time? This is an essential first step.

(2) Obvious things: use range rather than xrange in your loops. Make
sure that all heavily used variables/functions are local to the
function you're using them in. E.g., you use range, min and abs in
the middle of the 'brent' function. Instead, start the brent function
by setting _abs, _range, _min = abs, range, min, and then use _abs,
_range, etc. instead. Lookups of local variables are faster than
globals.

(3) In the inner loop:

for i in range(min(m,r-k)):
y,q=(y*y+c)%n,q*abs(x-y)%n

you can get probably rid of the abs call. It *might* also help to
avoid the tuple packing/unpacking (but see (1)). You could try doing
a couple of steps at a time instead of one (i.e., unroll the loop a
little bit); one advantage is that you probably don't need to bother
reducing q modulo n at every step; every other step would be good
enough. Depending on the relative speed of multiplication and
reduction, and the sizes of the integers involved, this might save
time.

(4) Have you tried using Montgomery reduction in the Brent method?
The inner loop of that method involves two reductions modulo n, which
may well be where the biggest bottleneck is. But see (1). The other
obvious bottleneck is the gcd method; if profiling shows that that's
the case, there might be ways to speed that up, too. (E.g., use a
binary gcd algorithm, or use Lehmer's method.)

Good luck!

 

[Aahz]

(2) Obvious things: use range rather than xrange in your loops.

Um, what? You meant the reverse, surely?

 

[Steve Howell]

Hello everyone. I am new to python and previously i did programming in
c/c++.Could some one please help me to improve the run time for this
python program as i don't have idea how to optimized this code.
[...]

How much of a speedup do you need?  Are we talking about orders of
magnitude (in which case you might want to consider using something
like the Multiple Polynomial Quadratic Sieve method instead, or as
well), or just a few percent?

(1) Have you profiled the code to see where it's spending most of its
time?  This is an essential first step.

I ditto the profiling recommendation.

http://docs.python.org/library/profile.html

It might also be useful to time your algorithm for n=10, 100, 1000,
10000, etc., to get a better sense of how the overall algorithm
behaves.

 

[Mark Dickinson]

Um, what?  You meant the reverse, surely?

Er, yes I did. Thanks!

 

[Mark Dickinson]

Hello everyone. I am new to python and previously i did programming in
c/c++.Could some one please help me to improve the run time for this
python program as i don't have idea how to optimized this code.This
code also seems to be more unpythonic so how to make it look like more
pythonic . I am trying for this problem(https://www.spoj.pl/problems/
FACT1/).
Thank you

One other thing: in the 'brent' function, you're setting m to
randrange(1, n). What's the purpose of this? It looks to me as
though m controls the number of Pollard-Rho iterations that are
clumped together at one time (before doing a gcd operation), and using
a random number for this doesn't make a lot of sense to me.

 

[Steve Howell]

One other thing:  in the 'brent' function, you're setting m to
randrange(1, n).  What's the purpose of this?  It looks to me as
though m controls the number of Pollard-Rho iterations that are
clumped together at one time (before doing a gcd operation), and using
a random number for this doesn't make a lot of sense to me.

The randomness also makes the algorithm a little buggy.

I tried this input:

37^5 41^5

Usually I get the right answer. Other times I get this:

37^5 41^3 1681^1

And occasionally it appears to get into an infinite loop, which
definitely could be a cause of "slowness."

 

[mukesh tiwari]

The randomness also makes the algorithm a little buggy.

I tried this input:

37^5 41^5

Usually I get the right answer.  Other times I get this:

37^5 41^3 1681^1

And occasionally it appears to get into an infinite loop, which
definitely could be a cause of "slowness."

Thank you all for help. I will try to improve these short comings.

 

[Paul Boddie]

I ditto the profiling recommendation.

http://docs.python.org/library/profile.html

(To the original inquirer...) Try this, too:

http://wiki.python.org/moin/PythonSpeed/Profiling

If you have the tools, it's a lot easier than scanning through tables
of times.

Paul