summaryrefslogtreecommitdiff
path: root/PlaygroundCpp
diff options
context:
space:
mode:
authorHaidong Ji2018-08-26 22:44:39 -0500
committerHaidong Ji2018-08-26 22:44:39 -0500
commite3fa94bc66937292fea1c49c677c672e2fdd654a (patch)
tree4684ce7d62fe1760b171f08ea6ba03c4e343c14e /PlaygroundCpp
parent1b625dab2d7b56e6b8d3289a0726724b3830e6b7 (diff)
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!!!
Diffstat (limited to 'PlaygroundCpp')
-rw-r--r--PlaygroundCpp/Sources/Playground.cpp67
1 files changed, 51 insertions, 16 deletions
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';
}