22

So, If i would like to calculate the value of 6^8 mod 5 using the pow function, what should I put in a line??

In the assumption that You don't need to import it first

I know that pow is used like pow (x, y) = pow (6, 8) = 6^8 and

My guess is 

mod.pow(6,8)

Thank you!

mark T
  • 243
  • 1
  • 2
  • 5

3 Answers3

46

It's simple: pow takes an optional 3rd argument for the modulus.

From the docs:

pow(x, y[, z])

Return x to the power y; if z is present, return x to the power y, modulo z (computed more efficiently than pow(x, y) % z). The two-argument form pow(x, y) is equivalent to using the power operator: x**y.

So you want:

pow(6, 8, 5)

Not only is pow(x, y, z) faster & more efficient than (x ** y) % z it can easily handle large values of y without using arbitrary precision arithmetic, assuming z is a simple machine integer.

PM 2Ring
  • 54,345
  • 6
  • 82
  • 182
  • 2
    Note that in version 3.8+: For int operands, the three-argument form of pow now allows the second argument to be negative, permitting computation of modular inverses. And keyword arguments are now permitted. Formerly, only positional arguments were supported. – PM 2Ring Aug 23 '20 at 14:00
  • Thank you so much! With your help I managed to calculate pow(3, 545918790 // 3, 10**9+7) just in time. – yo1995 Mar 28 '21 at 04:08
  • speed tested and found false. it is slower than `(x**y)%z` – ishandutta2007 Jan 05 '23 at 09:00
  • 1
    @ishandutta2007 Try it with smallish `x` and `z` (say, under 30 million) and large `y`. – PM 2Ring Jan 05 '23 at 09:16
  • small cases don't mean much to me. Time complexity is more dominated by the large case. If someone is using in a application where there are small cases only this might suffice but someone like me who needs coverage about large cases as well including arbitrary precision (ie beyond 128 bits), this wont. – ishandutta2007 Jan 14 '23 at 10:06
  • 1
    @ishandutta2007 But if x and y are large `(x ** y)` will cause a MemoryError, so you can't use that approach for arbitrary precision (eg, RSA calculations). – PM 2Ring Jan 14 '23 at 23:59
  • I don't remember what value I tested it with, but it was a moderate value not very large and I found `pow` is slower than `**`. My point is `pow` should handle all those cases internally and return the optimized result no matter what the user calls it with at least till python3.8 it is not so. Hopefully Guido van Rossum is reading this comment. – ishandutta2007 Jan 15 '23 at 07:35
  • @ishandutta2007 Perhaps, although the extra code needed to make that decision could make pow slower for the common case when the args are fairly small. I should mention that there's also a small overhead in making a function call vs invoking an operator. Fortunately, built-in functions (and many stdlib functions) are coded in C, and the overhead in calling a C function is not as bad as the overhead in calling a function coded in Python. (And of course a C function also executes faster than an equivalent Python function). – PM 2Ring Jan 15 '23 at 07:54
  • FWIW, `**` isn't as good as it could be, either. Eg, for positive integer `n`, `1< – PM 2Ring Jan 15 '23 at 07:57
8

check the docs of pow:

pow(6, 8, 5)

does what you want.

do not use a ** b % n! while this will give the correct result it will be by orders of magnitude slower if you do calculations for bigger numbers. pow will do the modulo operation in every step while ** will first do the exponentiation in the integers (which may result in a huge number) and take the modulus only at the end.

now if you are interested in numbers that are bigger than 32 bit you may want to have a look at gmpy2 for even more speed.

hiro protagonist
  • 44,693
  • 14
  • 86
  • 111
  • 3
    Thanks for mentioning gmpy2. Another arbitrary precision package worth looking at is [mpmath](http://mpmath.org), if you want fancy functions, root solving, integrals, etc. FWIW, mpmath will use gmpy, if it's available. – PM 2Ring Sep 23 '15 at 11:56
-1

You can use '%' character to get the modulo value. For example print(pow(6,8) % 5) or print(6**8 % 5).

EluciusFTW
  • 2,565
  • 6
  • 42
  • 59
Syed Ashraf
  • 7
  • 1