From e3fa94bc66937292fea1c49c677c672e2fdd654a Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Sun, 26 Aug 2018 22:44:39 -0500
Subject: Huge Fib mod M done!

This was so much fun! I'm glad I did it with Python, Java, and C++, in
that order. I learned so much through the process: typing, overflow,
BigInteger, and ended up not needing BigInteger! Yay!!!---
 PlaygroundCpp/Sources/Playground.cpp | 67 +++++++++++++++++++++++++++---------
 1 file changed, 51 insertions(+), 16 deletions(-)

(limited to 'PlaygroundCpp/Sources')

diff --git a/PlaygroundCpp/Sources/Playground.cpp b/PlaygroundCpp/Sources/Playground.cpp
index caa008b..35ce7da 100644
--- a/PlaygroundCpp/Sources/Playground.cpp
+++ b/PlaygroundCpp/Sources/Playground.cpp
@@ -1,29 +1,63 @@
 #include <iostream>
 //#include <gtest/gtest.h>
 
-static int getGCD(int a, int b) {
-	if (b == 0) {
-		return a;
-	}
+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;
 
-	if (b > a) {
-		return getGCD(b, a);
-	} else {
-		return getGCD(b, a % b);
+	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;
+}
+static int getFibNModM(long n, int m) {
+	int p = getPisanoPeriodOptimized(m);
+	long r = n % p;
+	if (r == 0)
+		return 0;
+	int firstN = 0;
+	int secondN = 1;
+	int tempHolder = 1;
+	for (int i = 1; i < r; i++) {
+		tempHolder = (firstN + secondN) % m;
+		firstN = secondN;
+		secondN = tempHolder;
 	}
+	return secondN;
 }
+
 //TEST(FibLastDigitTest, Zero) {
-//	ASSERT_EQ(getGCD(18, 35), 1);
+//	ASSERT_EQ(getFibNModM(2015, 3), 1);
 //}
 //
 //TEST(FibLastDigitTest, One) {
-//	ASSERT_EQ(17657, getGCD(28851538, 1183019));
+//	ASSERT_EQ(getFibNModM(239, 1000), 161);
 //}
 //
 //TEST(FibLastDigitTest, Three) {
-//	ASSERT_EQ(7, getGCD(1344, 217));
+//	ASSERT_EQ(getFibNModM(2816213588, 30524), 10249);
 //}
-//
+
 //TEST(FibLastDigitTest, Forty) {
 //	ASSERT_EQ(1344, getGCD(1344, 1344));
 //}
@@ -37,9 +71,10 @@ static int getGCD(int a, int b) {
 //}
 
 int main() {
-	int a, b;
-	std::cin >> a;
-	std::cin >> b;
-	int c = getGCD(a, b);
+	long n;
+	int m;
+	std::cin >> n;
+	std::cin >> m;
+	int c = getFibNModM(n, m);
 	std::cout << c << '\n';
 }
-- 
cgit v1.2.3