Added FastPower

DDullahan · DDullahan · commit 7216f28cb318 · 2019-04-08T08:57:34.000+08:00
Added FastPower
diff --git a/src/main/java/com/Others/FastPower.java b/src/main/java/com/Others/FastPower.java
@@ -0,0 +1,37 @@
+package src.main.java.com.Others;
+
+import java.math.BigInteger;
+
+/**
+ * We may calculate power with loops, but what if the index is too large ?
+ * FastPower aims to calculate quickly in this circumstances with time complexity O(log k),
+ * where k is the index.
+ *
+ * @author DDullahan
+ */
+public class FastPower {
+    public static BigInteger calculate(BigInteger n, BigInteger k, BigInteger mod) {
+        BigInteger ans = BigInteger.ONE;
+        while (!k.equals(BigInteger.ZERO)) {
+            int odd = k.mod(new BigInteger("2")).compareTo(BigInteger.ZERO);
+            if(odd == 1){
+                ans = ans.multiply(n).mod(mod);
+            }
+            k = k.divide(new BigInteger("2"));
+            n = n.multiply(n).mod(mod);
+        }
+        return ans.mod(mod);
+    }
+
+    public static long calculate(long n, long k, long mod) {
+        long ans = 1;
+        while (k != 0) {
+            if (k % 2 == 1) {
+                ans = (ans * n) % mod;
+            }
+            k >>= 1;
+            n = (n * n) % mod;
+        }
+        return ans % mod;
+    }
+}
diff --git a/src/main/java/com/Others/FastPowerTest.java b/src/main/java/com/Others/FastPowerTest.java
@@ -0,0 +1,40 @@
+package src.main.java.com.Others;
+
+import org.junit.*;
+
+import java.math.BigInteger;
+
+import static org.junit.Assert.*;
+
+public class FastPowerTest {
+
+    @Test
+    public void test() {
+        System.out.println("Long Type:");
+        long result;
+        result = FastPower.calculate(2, 2, 10);
+        assertEquals(result, 4);
+        System.out.println("The result of power(2,2) mod 10 is " + result);
+
+        result = FastPower.calculate(100, 1000, 20);
+        assertEquals(result, 0);
+        System.out.println("The result of power(100, 1000) mod 20 is " + result);
+
+        result = FastPower.calculate(123456, 123456789, 234);
+        System.out.println("The result of power(123456, 123456789) mod 234 is " + result);
+
+
+        System.out.println("BigInteger Type:");
+        BigInteger bigResult;
+        bigResult = FastPower.calculate(BigInteger.TEN, BigInteger.TEN, new BigInteger("4"));
+        assertEquals(bigResult, BigInteger.ZERO);
+        System.out.println("The bigResult of power(10, 10) mod 4 is " + bigResult);
+
+        bigResult = FastPower.calculate(new BigInteger("123456"), new BigInteger("123456789"), new BigInteger("234"));
+        System.out.println("The bigResult of power(123456, 123456789) mod 234 is " + bigResult);
+
+        bigResult = FastPower.calculate(new BigInteger("123456789101112"), new BigInteger("12345678910111213"), new BigInteger("567890"));
+        System.out.println("The bigResult of power(123456789101112, 12345678910111213) mod 567890 is " + bigResult);
+
+    }
+}
