1 
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.

Improve this question
12
  • 4
    run each case a million times and see the difference Commented Jan 19, 2020 at 18:36
  • 1
    @DYZ But he only has one implementation. Are you overlooking the // c in what he's asking about? Commented Jan 19, 2020 at 18:47
  • 1
    Given that almost everyone here misunderstood the question and overlooked what you were really asking about, it would be good if you edited the question to make it clear. Commented Jan 19, 2020 at 20:53
  • 1
    is it really a bottleneck in your program? if so you should consider using numpy if you have a lot of calculations like that, or use Cython, or write Python C/C++ extension, etc., but now your questions looks like XY problem Commented Jan 19, 2020 at 22:16
  • 2
    Please clarify whether a ** b-1 means a**(b-1) or (a**b)-1. Commented Jan 19, 2020 at 22:19

1 Answer 1

Reset to default
1

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
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Very nice. I had actually guessed this, but somehow dismissed it without even testing it. Silly me :-)
I think you missed the -1 in the equation as this works without the subtraction but not with it as the -1 is not part of the exponent but it is done after exponentiation, yet this is close.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.