From 35812b1161b5855d3b733fa6d499345dd14794fd Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Thu, 23 Aug 2018 21:37:29 -0500
Subject: 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.---
 .../sources/FibAgain.java                          |  62 ++++++++++++
 .../tests/FibAgainTest.java                        | 109 +++++++++++++++++++++
 .../tests/FibonacciTest.java                       |   5 +
 3 files changed, 176 insertions(+)
 create mode 100644 AlgoDesignAndTechniqueEdxJava/sources/FibAgain.java
 create mode 100644 AlgoDesignAndTechniqueEdxJava/tests/FibAgainTest.java

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));
+	}
+	
 }
-- 
cgit v1.2.3