diff options
| -rw-r--r-- | AlgoDesignAndTechniqueEdxPython/sources/fibagain.py | 64 | ||||
| -rw-r--r-- | AlgoDesignAndTechniqueEdxPython/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 |