[FEATURE REQUEST] <Optimizing Power (base^exponent)%mod using 2k-ary method Algorithm> #4424
Description
What would you like to Propose?
New Algorithm under https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/
File Name: PowerUsing2k_aryAlgorithm.java
What ?
To calculate long pow(int base, int exponent, int mod) , where mod is a prime number to avoid long overflow issues.
Why ?
Brute-force approach proposed in /maths/PowerUsingRecursion.java takes Time complexity : O(exponent) time.
Binary Exponentiation algorithm takes Time Complexity : O(log(exponent)) time , Aux-Space Complexity: O(log(exponent))
2k-ary method Algorithm takes Time Complexity : O(log(exponent)) time , Aux-Space Complexity: O(1)
Issue details
Link for Algorithm:
https://en.wikipedia.org/wiki/Exponentiation_by_squaring
How ?
Iterative Approach:
TC: O(log(exponent)) SC: O(1)
public long pow(int base, int exp, int mod)
{
long t = 1L;
while (exp > 0) {
// for cases where exponent
// is not an even value
if (exp % 2 != 0)
t = (t * base) % mod;
base = (base * base) % mod;
exp /= 2;
}
return t % mod;
}
Additional Information
No response