Modular exponentiation

“architectural photography of white building” by Benjamin Bousquet on Unsplash

Say you are required to code up:
(a ^ b) % c

Now why do “% c” after exponentiation, because a ^ b will be really large even for relatively small values of a, b and that is a problem because the data type of the language that we try to code the problem, will most probably not let us store such a large number.

Also (m * n) % p has a very interesting property:
(m * n) % p =((m % p) * (n % p)) % p

if b is even:
(a ^ b) % c = ((a ^ b/2) * (a ^ b/2))%c → this suggests divide and conquer

if b is odd:
(a ^ b) % c = (a * (a ^( b-1))%c

If we have to return the mod of a negative number x whose absolute value is less than y:
then (x + y) % y will do the trick

also as the product of (a ^ b/2) * (a ^ b/2) and a * (a ^( b-1) may cause overflow, hence we must be careful about those scenarios

C++ code:

For more posts like this follow me and do check out my other content. Happy coding!!

--

--

Re-learning the fundamentals of programming.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store