From 17882a58118516bce30522e05d47e8fbce76975e Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Sun, 26 Aug 2018 22:14:51 -0500
Subject: More improvement: not calculating fib at all!

Doing the first few in a spreadsheet (and properly label columns and
rows) really helped.---
 .../sources/fibagain.py                            | 64 ++++++++++++++--------
 .../tests/fibagainTest.py                          | 13 +++--
 2 files changed, 48 insertions(+), 29 deletions(-)

diff --git a/AlgoDesignAndTechniqueEdxPython/sources/fibagain.py b/AlgoDesignAndTechniqueEdxPython/sources/fibagain.py
index 53c18b9..86b5152 100644
--- a/AlgoDesignAndTechniqueEdxPython/sources/fibagain.py
+++ b/AlgoDesignAndTechniqueEdxPython/sources/fibagain.py
@@ -1,27 +1,29 @@
 # 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 getFibOptimized(n):
-    if (n <= 1):
-        return n
-    firstFib = 0
-    secondFib = 1
-    tempHolder = 1
-    for j in range(2, n + 1):
-        tempHolder = firstFib + secondFib
-        firstFib = secondFib
-        secondFib = tempHolder
-    return secondFib
+
+# 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 getFibOptimized(n):
+#     if (n <= 1):
+#         return n
+#     firstFib = 0
+#     secondFib = 1
+#     tempHolder = 1
+#     for _ in range(2, n + 1):
+#         tempHolder = firstFib + secondFib
+#         firstFib = secondFib
+#         secondFib = tempHolder
+#     return secondFib
 
 
 def getPisanoPeriod(m):
@@ -29,7 +31,7 @@ def getPisanoPeriod(m):
     remainder1 = 1
     remainder2 = 1
     
-    for i in range(3, 6 * m + 1):
+    for _ in range(3, 6 * m + 1):
         period = period + 1
         if (remainder2 == 1) & (remainder1 + remainder2 == m):
             break
@@ -45,12 +47,26 @@ def getPisanoPeriod(m):
 
 
 def getFibNModM(n, m):
+    # https://medium.com/competitive/huge-fibonacci-number-modulo-m-6b4926a5c836
+    # the above link helped me in improving my code
     p = getPisanoPeriod(m)
-    return getFibOptimized(n % p) % m
+    r = n % p
+    if r == 0:
+        return 0
+    firstN = 0
+    secondN = 1
+    tempHolder = 1
+    for _ in range(2, r + 1):
+        tempHolder = (firstN + secondN) % m;
+        firstN = secondN
+        secondN = tempHolder
+#     return getFibOptimized(n % p) % m
+    return secondN
+
 
 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
+    print(getFibNModM(n, m))
diff --git a/AlgoDesignAndTechniqueEdxPython/tests/fibagainTest.py b/AlgoDesignAndTechniqueEdxPython/tests/fibagainTest.py
index edcc5ba..2702bdb 100644
--- a/AlgoDesignAndTechniqueEdxPython/tests/fibagainTest.py
+++ b/AlgoDesignAndTechniqueEdxPython/tests/fibagainTest.py
@@ -12,22 +12,25 @@ 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)
 
+    def testFibNModM99999999999999999_2(self):
+        self.assertEqual(getFibNModM(99999999999999999, 2), 0)
+
 if __name__ == "__main__":
     #import sys;sys.argv = ['', 'Test.testName']
     unittest.main()
\ No newline at end of file
-- 
cgit v1.2.3