CODEWITHSUNDEEP
pythonc++loopspython-3.xoptimization
f zqf
f zqf

Reputation: 1

Python for for loops Optimisation

so I got a piece of code on which I try ways to make it run faster...because it takes roughtly 40 seconds to execute :

for i in range (1, len(pk), 2): for j in range (2, len(pk), 2): b = random.randrange(2 ** Const.ALPHA) sum += (b * pk[i] * pk[j])

I tried Threads...it doesnt run any faster. I tried to used sum() with the two for loops embbeded in it. It doesnt run any faster either.

pk elements are very large int.

Right now, len(pk) is equal to 162 and Const.ALPHA is equal to 9. But in the future, it might very well be more than that.

Thx

PS : Btw, you get a cookie if you can guess what's the purpose of the program using these variables.

Upvotes: 0

Views: 79

Answers (1)

rici
rici

Reputation: 241691

I don't have an i7 :) and I don't know how big your numbers are. I tried it with 65536-bit pk[i], and your function took almost 10.5 seconds, so I suppose your numbers are still a lot bigger.

But I think the results should be indicative. The function below took 0.45 seconds (for a better than 20x speed-up); it avoids multiplying bignums by turning sum(sum(r(b)*pk[i]*pk[j])) into sum(pk[i]*sum(r(b)*pk[j])). Not only does this do fewer multiplications, the majority of the multiplications which are left are smallnum * bignum instead of bignum * bignum.

The use of generators and list comprehensions might not help. YMMV.

def xmul(pk):
  # The speedup from these locals is insignificant, but
  # it lets the inline generator fit on a line.
  rmax = 2**const.ALPHA
  r = random.randrange
  return sum(
        pki * sum(r(rmax) * pkj for pkj in pk[2::2])
        for pki in pk[1::2]
  )

Upvotes: 2

Related Questions