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!

2 files changed, 77 insertions, 0 deletions

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