From 0cb94b3d22347b099b19cbf9bdfd4179d3a5c148 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Thu, 23 Aug 2018 19:48:29 -0500
Subject: Done!

I actually started implementing this in Java first, but ran into long
int overflow issues. Decided to get it working in Python first. I'm glad
it worked! Now back to implement it in Java!---
 .../sources/fibagain.py                            | 44 ++++++++++++++++++++++
 .../tests/fibagainTest.py                          | 33 ++++++++++++++++
 2 files changed, 77 insertions(+)
 create mode 100644 AlgoDesignAndTechniqueEdxPython/sources/fibagain.py
 create mode 100644 AlgoDesignAndTechniqueEdxPython/tests/fibagainTest.py

diff --git a/AlgoDesignAndTechniqueEdxPython/sources/fibagain.py b/AlgoDesignAndTechniqueEdxPython/sources/fibagain.py
new file mode 100644
index 0000000..2f2c839
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/sources/fibagain.py
@@ -0,0 +1,44 @@
+# Uses python3
+import sys
+
+def getFib(n):
+    if (n <= 1):
+        return n
+    fibLst = [None] * (n + 1)
+    fibLst[0] = 0
+    fibLst[1] = 1
+    for j in range(2, n + 1):
+        fibLst[j] = fibLst[j - 1] + fibLst[j - 2]
+    return fibLst[n]
+
+
+def getPisanoPeriod(m):
+    period = 2
+    remainder1 = 1
+    remainder2 = 1
+    
+    for i in range(3, 6 * m + 1):
+        period = period + 1
+        if (remainder2 == 1) & (remainder1 + remainder2 == m):
+            break
+        else:
+            tempHolder = remainder1 + remainder2
+            remainder1 = remainder2
+            if tempHolder >= m:
+                remainder2 = tempHolder - m
+            else:
+                remainder2 = tempHolder
+                
+    return period
+
+
+def getFibNModM(n, m):
+    p = getPisanoPeriod(m)
+    return getFib(n % p) % m
+
+if __name__ == '__main__':
+    entryNumbers = sys.stdin.read()
+    tokens = entryNumbers.split()
+    n = int(tokens[0])
+    m = int(tokens[1])
+    print(getFibNModM(n, m))
\ No newline at end of file
diff --git a/AlgoDesignAndTechniqueEdxPython/tests/fibagainTest.py b/AlgoDesignAndTechniqueEdxPython/tests/fibagainTest.py
new file mode 100644
index 0000000..edcc5ba
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/tests/fibagainTest.py
@@ -0,0 +1,33 @@
+'''
+Created on Aug 23, 2018
+
+@author: haidong
+'''
+import unittest
+
+from sources.fibagain import getPisanoPeriod, getFibNModM
+
+class Test(unittest.TestCase):
+
+
+    def testPisanoPeriod73(self):
+        self.assertEqual(getPisanoPeriod(73), 148)
+
+    def testPisanoPeriod2(self):
+        self.assertEqual(getPisanoPeriod(2), 3)
+
+    def testPisanoPeriod98(self):
+        self.assertEqual(getPisanoPeriod(98), 336)
+    
+    def testFibNModM2015_3(self):
+        self.assertEqual(getFibNModM(2015, 3), 1)
+
+    def testFibNModM239_1000(self):
+        self.assertEqual(getFibNModM(239, 1000), 161)
+
+    def testFibNModM2816213588_30524(self):
+        self.assertEqual(getFibNModM(2816213588, 30524), 10249)
+
+if __name__ == "__main__":
+    #import sys;sys.argv = ['', 'Test.testName']
+    unittest.main()
\ No newline at end of file
-- 
cgit v1.2.3