java-algorithms-implementation/src/com/jwetherell/algorithms/mathematics/Exponentiation.java at master · phishman3579/java-algorithms-implementation · GitHub

Name: java-algorithms-implementation/src/com/jwetherell/algorithms/mathematics/Exponentiation.java at master · phishman3579/java-algorithms-implementation · GitHub
Rating: 4.9 (9257 reviews)
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
packagecom.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 <mail@bartlomiejdrozd.pl>
 * @author Justin Wetherell <phishman3579@gmail.com>
 */
publicclassExponentiation {

publicstaticintrecursiveExponentiation(intbase, intexponent) {
if (exponent == 0)
return1;
if (exponent == 1)
returnbase;

returnrecursiveExponentiation(base, exponent - 1) * base;
 }

publicstaticintfastRecursiveExponentiation(intbase, intexponent) {
if (exponent == 0)
return1;
if (exponent == 1)
returnbase;

finalintresultOnHalfExponent = fastRecursiveExponentiation(base, exponent / 2);
if ((exponent % 2) == 0)
returnresultOnHalfExponent * resultOnHalfExponent;
else
returnresultOnHalfExponent * resultOnHalfExponent * base;

 }

publicstaticintfastRecursiveExponentiationModulo(intbase, intexponent, intmod) {
if (exponent == 0)
return1;
if (exponent == 1)
returnbase;

finalintresultOnHalfExponent = fastRecursiveExponentiationModulo(base, exponent / 2, mod);
if ((exponent % 2) == 0)
return (resultOnHalfExponent * resultOnHalfExponent) % mod;
else
return (((resultOnHalfExponent * resultOnHalfExponent) % mod) * base) % mod;
 }
}