Python Optimization

[Mark Dickinson]

On Feb 14, 4:53 pm, mukesh tiwari <mukeshtiwari.ii... at gmail.com>
wrote:
> 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!
--
Mark