summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2018-08-23 21:37:29 -0500
committerHaidong Ji2018-08-23 21:37:29 -0500
commit35812b1161b5855d3b733fa6d499345dd14794fd (patch)
treed814ec260fb8e4ec7eb2495ef70f61af4086e150
parentb3a6f3bc47098c81bef2c7d16690a5801149dbd8 (diff)
Done!
Reinplemented so that fib is of type BigInteger. With this I was able to get big Fib(n) mod m working. In this particular case, it felt easier with Python, since it is dynamic, not strongly typed.
-rw-r--r--AlgoDesignAndTechniqueEdxJava/sources/FibAgain.java62
-rw-r--r--AlgoDesignAndTechniqueEdxJava/tests/FibAgainTest.java109
-rw-r--r--AlgoDesignAndTechniqueEdxJava/tests/FibonacciTest.java5
3 files changed, 176 insertions, 0 deletions
diff --git a/AlgoDesignAndTechniqueEdxJava/sources/FibAgain.java b/AlgoDesignAndTechniqueEdxJava/sources/FibAgain.java
new file mode 100644
index 0000000..fbf907e
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/sources/FibAgain.java
@@ -0,0 +1,62 @@
+import java.math.BigInteger;
+import java.util.Scanner;
+
+public class FibAgain {
+
+ public static BigInteger getFib(int n) {
+ if (n <= 1)
+ return BigInteger.valueOf(n);
+ final BigInteger[] fibArray = new BigInteger[n + 1];
+ fibArray[0] = BigInteger.valueOf(0);
+ fibArray[1] = BigInteger.valueOf(1);
+ for (int i = 2; i < n + 1; i++) {
+ fibArray[i] = fibArray[i - 1].add(fibArray[i - 2]);
+ }
+ return fibArray[n];
+ }
+
+ public static int getPisanoPeriodOptimized(int m) {
+ // this optimized algorithm is obtained through the
+ // discussion starting around 7:30 mark of the following
+ // video. We know the upper bound for the loop, which
+ // is 6*m, through articles listed above
+ // https://www.youtube.com/watch?v=Nu-lW-Ifyec
+ // https://en.wikipedia.org/wiki/Pisano_period
+ // The unoptimized naive algorithm looks for modulus
+ // 0 followed by 1
+ int period = 2;
+ int remainder1 = 1;
+ int remainder2 = 1;
+
+ for (int i = 3; i <= 6 * m; i++) {
+ period++;
+ if (remainder2 == 1 && (remainder1 + remainder2 == m)) {
+ break;
+ } else {
+ int tempHolder = remainder1 + remainder2;
+ remainder1 = remainder2;
+ if (tempHolder >= m) {
+ remainder2 = tempHolder - m;
+ } else {
+ remainder2 = tempHolder;
+ }
+ }
+ }
+ return period;
+ }
+
+ public static int getFibNModM(long n, int m) {
+ int p = getPisanoPeriodOptimized(m);
+ long i = n % p;
+ BigInteger fib = getFib((int) i);
+ return fib.mod(BigInteger.valueOf(m)).intValue();
+ }
+
+ public static void main(String args[]) {
+ Scanner in = new Scanner(System.in);
+ long n = in.nextLong();
+ int m = in.nextInt();
+
+ System.out.println(getFibNModM(n, m));
+ }
+}
diff --git a/AlgoDesignAndTechniqueEdxJava/tests/FibAgainTest.java b/AlgoDesignAndTechniqueEdxJava/tests/FibAgainTest.java
new file mode 100644
index 0000000..de32b49
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/tests/FibAgainTest.java
@@ -0,0 +1,109 @@
+import static org.junit.jupiter.api.Assertions.*;
+
+import java.math.BigInteger;
+
+import org.junit.jupiter.api.Test;
+
+public class FibAgainTest {
+ @Test
+ void testGetFib40() {
+ BigInteger f = new BigInteger("102334155");
+ assertEquals(f, FibAgain.getFib(40));
+ }
+
+ @Test
+ void testFibonacciPisanoPeriodOptimized2() {
+ assertEquals(3, FibAgain.getPisanoPeriodOptimized(2));
+ }
+
+ @Test
+ void testFibonacciPisanoPeriodOptimized3() {
+ assertEquals(8, FibAgain.getPisanoPeriodOptimized(3));
+ }
+
+ @Test
+ void testFibonacciPisanoPeriod4() {
+ assertEquals(6, FibAgain.getPisanoPeriodOptimized(4));
+ }
+
+ @Test
+ void testFibonacciPisanoPeriod5() {
+ assertEquals(20, FibAgain.getPisanoPeriodOptimized(5));
+ }
+
+ @Test
+ void testFibonacciPisanoPeriod7() {
+ assertEquals(16, FibAgain.getPisanoPeriodOptimized(7));
+ }
+
+ @Test
+ void testFibonacciPisanoPeriod10() {
+ assertEquals(60, FibAgain.getPisanoPeriodOptimized(10));
+ }
+
+ @Test
+ void testFibonacciPisanoPeriod50() {
+ assertEquals(300, FibAgain.getPisanoPeriodOptimized(50));
+ }
+
+ @Test
+ void testFibonacciPisanoPeriod100() {
+ assertEquals(300, FibAgain.getPisanoPeriodOptimized(100));
+ }
+
+ @Test
+ void testFibonacciPisanoPeriod133() {
+ assertEquals(144, FibAgain.getPisanoPeriodOptimized(133));
+ }
+
+ @Test
+ void testFibonacciPisanoPeriod98() {
+ assertEquals(336, FibAgain.getPisanoPeriodOptimized(98));
+ }
+
+ @Test
+ void testFibonacciPisanoPeriod74() {
+ assertEquals(228, FibAgain.getPisanoPeriodOptimized(74));
+ }
+
+ @Test
+ void testFibonacciPisanoPeriod62() {
+ assertEquals(30, FibAgain.getPisanoPeriodOptimized(62));
+ }
+
+ @Test
+ void testFibonacciPisanoPeriod68() {
+ assertEquals(36, FibAgain.getPisanoPeriodOptimized(68));
+ }
+
+ @Test
+ void testFibonacciPisanoPeriod71() {
+ assertEquals(70, FibAgain.getPisanoPeriodOptimized(71));
+ }
+
+ @Test
+ void testFibonacciPisanoPeriod72() {
+ assertEquals(24, FibAgain.getPisanoPeriodOptimized(72));
+ }
+
+ @Test
+ void testFibonacciPisanoPeriod73() {
+ assertEquals(148, FibAgain.getPisanoPeriodOptimized(73));
+ }
+
+
+ @Test
+ void testFibonacciFibNModM2015_3() {
+ assertEquals(1, FibAgain.getFibNModM(2015, 3));
+ }
+
+ @Test
+ void testFibonacciFibNModM239_1000() {
+ assertEquals(161, FibAgain.getFibNModM(239, 1000));
+ }
+
+ @Test
+ void testFibonacciFibNModM2816213588_30524() {
+ assertEquals(10249, FibAgain.getFibNModM(2816213588L, 30524));
+ }
+}
diff --git a/AlgoDesignAndTechniqueEdxJava/tests/FibonacciTest.java b/AlgoDesignAndTechniqueEdxJava/tests/FibonacciTest.java
index 52df692..73c1702 100644
--- a/AlgoDesignAndTechniqueEdxJava/tests/FibonacciTest.java
+++ b/AlgoDesignAndTechniqueEdxJava/tests/FibonacciTest.java
@@ -26,4 +26,9 @@ public class FibonacciTest {
assertEquals(102334155, Fibonacci.fib_optimized1(40));
}
+ @Test
+ void testFibonacci73() {
+ assertEquals(806515533049393L, Fibonacci.fib_optimized1(73));
+ }
+
}