modular exponentiation c++
// 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(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
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;
}
// This code is contributed by shubhamsingh10
/**
* Calculate a^n in O(logn) time, instead of O(n) time with naive approach.
**/
public static long powerRecursive(int base, int exponent){
if(exponent == 0) return 1;
return (exponent % 2 == 0) ?
powerRecursive(base, exponent / 2) * powerRecursive(base, exponent / 2)
: base * powerRecursive(base, (exponent - 1) / 2) *
powerRecursive(base, (exponent - 1) / 2);
}
