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.

1 files changed, 62 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));
+	}
+}