Friday, 28 May 2021

Python: speed up pow(base,exp,mod) for fixed exp and mod, or with vectorization

The bottleneck of my code is the repeated calling of pow(base,exponent,modulus) for very large integers (numpy does not support such large integers, about 100 to 256 bits). However, my exponent and modulus is always the same. Could I somehow utilize this to speed the computation up with a custom function? I tried to define a function as seen below (function below is for general modulus and exponent).

However, even if I hardcode every operation without the while-loop and if-statements for a fixed exponent and modulus, it is slower than pow.

def modular_pow(self, base, exponent, modulus):
    result = 1
    base = base % modulus
    while exponent > 0:
        if (exponent % 2 == 1):
            result = (result * base) % modulus
        exponent = exponent >> 1
        base = (base * base) % modulus
    return result

Another option would be if I can somehow "vectorize" it. I have to compute pow for about 100000000 different base values. While these values often change between my script runs (so a look up table will not be useful), I will know these values the moment I hit run (I could compute them all at once).

Any ideas? I got some speedup by using mpz datatypes from gmpy2, but it still is too slow.



from Python: speed up pow(base,exp,mod) for fixed exp and mod, or with vectorization

No comments:

Post a Comment