Algorithms : complete 01-algorithmic_toolbox 01-intro

1 files changed, 50 insertions, 3 deletions

diff --git a/01-algorithmic_toolbox/01-intro/05-fibonacci_huge/fibonacci_huge.cpp b/01-algorithmic_toolbox/01-intro/05-fibonacci_huge/fibonacci_huge.cpp
index db0c074..8a9a61c 100644
--- a/01-algorithmic_toolbox/01-intro/05-fibonacci_huge/fibonacci_huge.cpp
+++ b/01-algorithmic_toolbox/01-intro/05-fibonacci_huge/fibonacci_huge.cpp
@@ -1,8 +1,55 @@
 #include <iostream>
 
-long long get_fibonaccihuge(long long n, long long m) {
-  //write your code here
-  return 0;
+long long get_fibonaccihuge(long long n, long long m)
+{
+    long long a, b, c, i; //, r, g, R;
+    long long g;
+
+    // length of pisano period pi(m)
+    a = 0; b = 1;
+    g = 0;
+    /* Fi mod m */
+    for (i = 0; ; i++) {
+        c = a + b;
+        if (c >= m)
+            c -= m;
+        // start pattern is 011
+        if (c == 0)
+            g = ((g == 0) ? 1 : 0);
+        else if (g == 1)
+            g = ((c == 1) ? 2 : 0);
+        else if (g == 2) {
+            if (c == 1)
+                break;
+            g = 0;
+        }
+        /* if (g == 2) { */
+        /*     i += 1; */
+        /*     break; */
+        /* } */
+
+        a = b;
+        b = c;
+    }
+
+    /* g = n % i; */
+    g = (n / i);
+    g = n - (g * i);
+
+    if (g <= 1)
+        return g;
+
+    /* Fg mod m */
+    a = 0; b = 1;
+    for (i = 1; i < g; i++) {
+        c = a + b;
+        if (c >= m)
+            c -= m;
+        a = b;
+        b = c;
+    }
+
+    return b;
 }
 
 int main() {