1

When I put in Python interpreter a ** b % c with large a (20 figures) b (4 figures) c (20 figures) I saw that Python calculates it pretty fast, almost like pow (a,b,c). I expect another behavior that Python first calculate a ** b then get the modulo (%) of result and such calculation will take significantly more time.

Where is the magic behind the scene?

Community
  • 1
  • 1
Bole
  • 11
  • 1
  • 3
  • 1
    You can use `pow` to calculate `(x ** y) % z` efficiently. See http://stackoverflow.com/questions/101268/hidden-features-of-python/3371415#3371415 – Paolo Moretti Aug 10 '11 at 17:26

4 Answers4

6

If you are typing into the Python interpreter something like:

20937505974095709374 ** 3438

Then seeing a couple of seconds wait. Then trying:

20937505974095709374 ** 3438 % 6

And seeing no wait, and wondering why there is a difference, then the delay that you see in the first instance is actually the time your terminal takes to buffer and print the huge number you just created to the screen.

Chris Farmiloe
  • 13,935
  • 5
  • 48
  • 57
  • 1
    Yep, this is exactly the issue, as you can see by assigning each calculation to a variable rather than printing it. – kindall Aug 10 '11 at 17:33
4

20 figures is laughably small on a modern computer. Try 2000 figures and you might see a difference.

Also, this past question is related: How did Python implement the built-in function pow()?

Community
  • 1
  • 1
Nayuki
  • 17,911
  • 6
  • 53
  • 80
2

There is no magic behind the scenes, other than Python supports arbitrary-precision integers, and is well-implemented. It really did calculate a**b, then %c.

Ned Batchelder
  • 364,293
  • 75
  • 561
  • 662
0

Today's computers are amazingly fast, very complicated calculations can occur in what seems like no time at all. You need to repeat such calculations very many times to see the delay; I'd start with a million.

Mark Ransom
  • 299,747
  • 42
  • 398
  • 622