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.

marc_s
  • 732,580
  • 175
  • 1,330
  • 1,459
Laurens
  • 63
  • 3
  • 4
    run each case a million times and see the difference – unknown.prince Jan 19 '20 at 18:36
  • @DYZ What would you time, though? – Kelly Bundy Jan 19 '20 at 18:41
  • 1
    @DYZ But he only has *one* implementation. Are you overlooking the `// c` in what he's asking about? – Kelly Bundy Jan 19 '20 at 18:47
  • I feel that the OP has two implementations: `(a ** b-1) // c % b` and `a ** b % c`. But I may be wrong. – DYZ Jan 19 '20 at 19:22
  • @DYZ Those are two quite different expressions, they don't compute the same at all. Pretty sure he's just showing the latter together with `pow` to show what kind of improvement he has in mind. – Kelly Bundy Jan 19 '20 at 19:25
  • @HeapOverflow You are right, I tried to show what kind of improvement I had in mind, I know these are very different but they both use exponentiation and I only care about its value modulo a number, they are indeed not the same. I am not a mathematician but maybe one of you is and maybe someone knows a way to speedup the code using for example modular exponentiation. – Laurens Jan 19 '20 at 19:32
  • 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. – Kelly Bundy Jan 19 '20 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](https://meta.stackexchange.com/questions/66377/what-is-the-xy-problem) – Azat Ibrakov Jan 19 '20 at 22:16
  • 2
    Please clarify whether `a ** b-1` means `a**(b-1)` or `(a**b)-1`. – Kelly Bundy Jan 19 '20 at 22:19
  • @AzatIbrakov I think NumPy/Cython etc would be missing the point. Think of `17**123456789 % 13`. If you actually compute `17**123456789` first, it'll be very slow and take a lot of memory. That number is *huge*. But Python's built-in `pow(17, 123456789, 13)` computes the result *instantly*. Because it can reduce `% 13` all the time, keeping intermediary numbers very small. That's not the kind of thing NumPy/Cython are for, is it? And I'd say the goal here is to do `17**123456789 // 23 % 13` similarly efficiently, again without computing `17**123456789` or anything even mildly big. – Kelly Bundy Jan 19 '20 at 22:29
  • @laurensfrensen Just to be sure: Do you really want integer/floor division by c? Or are you actually working modulo b and should be *multiplying* with the *inverse* of c? – Kelly Bundy Jan 20 '20 at 05:34
  • @HeapOverflow: then it can be asked on https://math.stackexchange.com or https://cs.stackexchange.com, because it is just happened to be written in Python, underlying problem seems language independent to me, but there is [this thread](https://stackoverflow.com/questions/5246856/how-did-python-implement-the-built-in-function-pow) though – Azat Ibrakov Jan 20 '20 at 09:13

1 Answers1

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
mathfux
  • 5,759
  • 1
  • 14
  • 34
  • Very nice. I had actually guessed this, but somehow dismissed it without even testing it. Silly me :-) – Kelly Bundy Jan 20 '20 at 05:44
  • 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. – Laurens Jan 20 '20 at 10:03