-
Notifications
You must be signed in to change notification settings - Fork 1.8k
/
Exponentiation.java
60 lines (52 loc) · 2.04 KB
/
Exponentiation.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
package com.jwetherell.algorithms.mathematics;
/**
* Recursive function of exponentiation is just an implementation of definition.
* <p>
* @see <a href="https://en.wikipedia.org/wiki/Exponentiation">Exponentiation (Wikipedia)</a>
* <p>
* Complexity - O(N) where N is exponent.
* <p>
* Fast exponentiation's complexity is O(lg N)
* <p>
* @see <a href="https://en.wikipedia.org/wiki/Exponentiation_by_squaring">Exponentiation by Squaring (Wikipedia)</a>
* <br>
* Modular exponentiation is similar.
* <p>
* @see <a href="https://en.wikipedia.org/wiki/Modular_exponentiation">Modular Exponentiation (Wikipedia)</a>
* <p>
* This implementation is the fast version of this algorithm with a complexity of O(lg N) also
* <br>
* @author Bartlomiej Drozd <[email protected]>
* @author Justin Wetherell <[email protected]>
*/
public class Exponentiation {
public static int recursiveExponentiation(int base, int exponent) {
if (exponent == 0)
return 1;
if (exponent == 1)
return base;
return recursiveExponentiation(base, exponent - 1) * base;
}
public static int fastRecursiveExponentiation(int base, int exponent) {
if (exponent == 0)
return 1;
if (exponent == 1)
return base;
final int resultOnHalfExponent = fastRecursiveExponentiation(base, exponent / 2);
if ((exponent % 2) == 0)
return resultOnHalfExponent * resultOnHalfExponent;
else
return resultOnHalfExponent * resultOnHalfExponent * base;
}
public static int fastRecursiveExponentiationModulo(int base, int exponent, int mod) {
if (exponent == 0)
return 1;
if (exponent == 1)
return base;
final int resultOnHalfExponent = fastRecursiveExponentiationModulo(base, exponent / 2, mod);
if ((exponent % 2) == 0)
return (resultOnHalfExponent * resultOnHalfExponent) % mod;
else
return (((resultOnHalfExponent * resultOnHalfExponent) % mod) * base) % mod;
}
}