Modular Exponentiation (Power in Modular Arithmetic) - GeeksforGeeks
Given three numbers x, y and p, compute (xy) % p.
Time Complexity of optimized solution: O(logn)
Let us extend the pow function to work for negative y and float x.
Time Complexity: O(n)
Space Complexity: O(1)
Algorithmic Paradigm: Divide and conquer.
http://www.geeksforgeeks.org/write-an-iterative-olog-y-function-for-powx-y/
http://www.geeksforgeeks.org/modular-exponentiation-power-in-modular-arithmetic/
Read full article from Modular Exponentiation (Power in Modular Arithmetic) - GeeksforGeeks
Given three numbers x, y and p, compute (xy) % p.
Input: x = 2, y = 3, p = 5 Output: 3 Explanation: 2^3 % 5 = 8 % 5 = 3.It can be optimized to O(logn) by calculating power(x, y/2) only once and storing it.
/* Function to calculate x raised to the power y in O(logn)*/int power(int x, unsigned int y){ int temp; if( y == 0) return 1; temp = power(x, y/2); if (y%2 == 0) return temp*temp; else return x*temp*temp;} |
Let us extend the pow function to work for negative y and float x.
float power(float x, int y){ float temp; if( y == 0) return 1; temp = power(x, y/2); if (y%2 == 0) return temp*temp; else { if(y > 0) return x*temp*temp; else return (temp*temp)/x; }} Time Complexity: O(n)
Space Complexity: O(1)
Algorithmic Paradigm: Divide and conquer.
nt power(int x, unsigned int y){ if( y == 0) return 1; else if (y%2 == 0) return power(x, y/2)*power(x, y/2); else return x*power(x, y/2)*power(x, y/2);}/* Iterative Function to calculate (x^y) in O(logy) */int power(int x, unsigned int y){ int res = 1; // Initialize result while (y > 0) { // If y is odd, multiply x with result if (y & 1) res = res*x; // n must be even now y = y>>1; // y = y/2 x = x*x; // Change x to x^2 } return res;}
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.
(a mod p) (b mod p) ≡ (ab) mod p or equivalently ( (a mod p) (b mod p) ) mod p = (ab) mod p
int power(int 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 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;}