Search code examples
pythonperformanceexponentiationmodular-arithmetic

Can this script have better performance using modular exponentiation?


def f(a, b, c):
    return ((a ** b)-1) // c % b

Can this script be faster in some way? (I have been looking for something with modular exponentiation):

pow(a, b, c) == a ** b % c

but this above script doesn't seem to be improvable like that. Does anyone know a way to speedup the above script? Thanks in advance.

Edit:

The second script is not at all the same as the first one, it is just meant to show what kind of optimization I had in mind.

Edit:

I didn't put the exact equation in becouse I wanted a general case solution, the specfics are when a = 4 and c = 3. Does that make it easier?

Edit:

I got the request to make it clear if I want to subtract first or if I want to exponentiate first, I want to first do the exponentiation which I made clear by adding brackets.


Solution

  • Note that a**b//c%d == a**b%(c*d)//c%d holds for any positive integers. This is true because there exists a positive integer k such that a**b == k*c*d + a**b%(c*d) holds and result of operation //c%d over right side is not affected by any k. According to this fact, a**b//c%d can be calculated using a command

    pow(a,b,c*d)//c%d