From 0f13a35dee0df21f4c1a387b50582a958c7bc439 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= <jeremy@asynk.ch>
Date: Sun, 13 Nov 2016 20:29:59 +0100
Subject: Algorithms : complete 01-algorithmic_toolbox 01-intro

---
 .../01-intro/01-fibonacci/fibonacci.cpp            | 19 +++++++-
 .../fibonacci_last_digit.cpp                       | 19 +++++++-
 01-algorithmic_toolbox/01-intro/03-gcd/gcd.cpp     | 35 ++++++++++----
 01-algorithmic_toolbox/01-intro/04-lcm/lcm.cpp     | 34 ++++++++++++--
 .../01-intro/05-fibonacci_huge/fibonacci_huge.cpp  | 53 ++++++++++++++++++++--
 5 files changed, 141 insertions(+), 19 deletions(-)

diff --git a/01-algorithmic_toolbox/01-intro/01-fibonacci/fibonacci.cpp b/01-algorithmic_toolbox/01-intro/01-fibonacci/fibonacci.cpp
index adc7404..c2564b8 100644
--- a/01-algorithmic_toolbox/01-intro/01-fibonacci/fibonacci.cpp
+++ b/01-algorithmic_toolbox/01-intro/01-fibonacci/fibonacci.cpp
@@ -7,10 +7,27 @@ int calc_fib(int n) {
     return calc_fib(n - 1) + calc_fib(n - 2);
 }
 
+int fib(int n)
+{
+    int a, b, c, i;
+
+    if (n <= 1)
+        return n;
+
+    a = 0; b = 1;
+    for(i = 1; i < n; i++) {
+        c = a + b;
+        a = b;
+        b = c;
+    }
+
+    return b;
+}
+
 int main() {
     int n = 0;
     std::cin >> n;
 
-    std::cout << calc_fib(n) << '\n';
+    std::cout << fib(n) << '\n';
     return 0;
 }
diff --git a/01-algorithmic_toolbox/01-intro/02-fibonacci_last_digit/fibonacci_last_digit.cpp b/01-algorithmic_toolbox/01-intro/02-fibonacci_last_digit/fibonacci_last_digit.cpp
index 08e8dd8..f064113 100644
--- a/01-algorithmic_toolbox/01-intro/02-fibonacci_last_digit/fibonacci_last_digit.cpp
+++ b/01-algorithmic_toolbox/01-intro/02-fibonacci_last_digit/fibonacci_last_digit.cpp
@@ -1,8 +1,23 @@
 #include <iostream>
 
 int get_fibonacci_last_digit(int n) {
-  //write your code here
-  return 0;
+    int a, b, c, i;
+
+    if (n <= 1)
+        return n;
+
+    a = 0; b = 1;
+    for(i = 1; i < n; i++) {
+        c = a + b;
+        if (c >= 10)
+            c -= 10;
+        a = b;
+        b = c;
+    }
+    if (b >= 10)
+        b -= 10;
+
+    return b;
 }
 
 int main() {
diff --git a/01-algorithmic_toolbox/01-intro/03-gcd/gcd.cpp b/01-algorithmic_toolbox/01-intro/03-gcd/gcd.cpp
index f723be2..fc13392 100644
--- a/01-algorithmic_toolbox/01-intro/03-gcd/gcd.cpp
+++ b/01-algorithmic_toolbox/01-intro/03-gcd/gcd.cpp
@@ -1,16 +1,31 @@
 #include <iostream>
 
-int gcd(int a, int b) {
-  //write your code here
-  int current_gcd = 1;
-  for (int d = 2; d <= a && d <= b; d++) {
-    if (a % d == 0 && b % d == 0) {
-      if (d > current_gcd) {
-        current_gcd = d;
-      }
+int gcd(int a, int b)
+{
+    int d, r;
+
+    if ((a == b) || (a == 0))
+        return a;
+
+    if (b == 0)
+        return b;
+
+    if (b > a) {
+        d = a;
+        a = b;
+        b = d;
     }
-  }
-  return current_gcd;
+
+    for(;;) {
+        d = a / b;
+        r = a - (d * b);
+        if (r == 0)
+            break;
+        a = b;
+        b = r;
+    }
+
+    return b;
 }
 
 int main() {
diff --git a/01-algorithmic_toolbox/01-intro/04-lcm/lcm.cpp b/01-algorithmic_toolbox/01-intro/04-lcm/lcm.cpp
index c6f503c..62e7799 100644
--- a/01-algorithmic_toolbox/01-intro/04-lcm/lcm.cpp
+++ b/01-algorithmic_toolbox/01-intro/04-lcm/lcm.cpp
@@ -1,8 +1,36 @@
 #include <iostream>
 
-long long lcm(int a, int b) {
-  //write your code here
-  return a*b;
+long long gcd(int a, int b)
+{
+    long long d, r;
+
+    if ((a == b) || (a == 0))
+        return a;
+
+    if (b == 0)
+        return b;
+
+    if (b > a) {
+        d = a;
+        a = b;
+        b = d;
+    }
+
+    for(;;) {
+        d = a / b;
+        r = a - (d * b);
+        if (r == 0)
+            break;
+        a = b;
+        b = r;
+    }
+
+    return (long long) b;
+}
+
+long long lcm(int a, int b)
+{
+    return (b / gcd(a, b)) * a;
 }
 
 int main() {
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() {
-- 
cgit v1.1-2-g2b99