Hello Everyone,
Given three numbers x, y and p, compute (xy) % p.
Examples :
Input: x = 2, y = 3, p = 5 Output: 3 Explanation: 2^3 % 5 = 8 % 5 = 3. Input: x = 2, y = 5, p = 13 Output: 6 Explanation: 2^5 % 13 = 32 % 13 = 6.
Below is discussed iterative solution.
/* Iterative Function to calculate (x^y) in O(log y) */
int power( int x, int y)
{
// Initialize answer
int res = 1;
// Check till the number becomes zero
while (y)
{
// If y is odd, multiply x with result
if (y % 2 == 1)
res = (res * x);
// y = y/2
y = y >> 1;
// Change x to x^2
x = (x * x);
}
return res;
}
Efficient Approach:
The problem with above solutions is, overflow may occur for large value of n or x. Therefore, power is generally evaluated under modulo of a large number.
Below is the fundamental modular property that is used for efficiently computing power under modular arithmetic.
(ab) mod p = ( (a mod p) (b mod p) ) mod p For example a = 50, b = 100, p = 13 50 mod 13 = 11 100 mod 13 = 9 (50 * 100) mod 13 = ( (50 mod 13) * (100 mod 13) ) mod 13 or (5000) mod 13 = ( 11 * 9 ) mod 13 or 8 = 8
Below is the implementation based on above property.
// Iterative C++ program to compute modular power
#include <iostream>
using namespace std;
/* Iterative Function to calculate (x^y)%p in O(log y) */
int power( long long x, unsigned int y, int p)
{
int res = 1; // Initialize result
x = x % p; // Update x if it is more than or
// equal to p
if (x == 0) return 0; // In case x is divisible by p;
while (y > 0)
{
// If y is odd, multiply x with result
if (y & 1)
res = (res*x) % p;
// y must be even now
y = y>>1; // y = y/2
x = (x*x) % p;
}
return res;
}
// Driver code
int main()
{
int x = 2;
int y = 5;
int p = 13;
cout << "Power is " << power(x, y, p);
return 0;
}
Output
Power is 6
Time Complexity of above solution is O(Log y).