src/algorithms/math/fibonacci/Q_matrix.js

@@ -0,0 +1,43 @@
+/**
+ * Calculate fibonacci number at specific position using Q matrix in O(logn) time.
+ *
+ * @param n
+ * @return {number}
+ */
+ export default function fibonacciNth(n) {
+
+  //Require math.js library. If you're from python background, it is equivalent to numpy
+  const math = require('mathjs');
+
+  //mod is just for our convenience to see how quick large values are getting computed
+  const M = math.matrix([[1,1],[1,0]]),
+        Q = M,
+        mod = 10 ** 9 + 7;
+
+  //Using Q^n = Q^n/2 * Q^n/2
+  const power = (Q,n) => {
+    if(n == 1){
+        return M;
+    }
+
+    Q = power(Q,Math.floor(n/2));
+    Q = math.mod(math.multiply(Q,Q),mod);
+    if(n % 2 != 0){
+        Q = math.mod(math.multiply(Q,M),mod);
+    }
+
+    return Q;
+
+}
+
+  const fibonacci = (Q,n) => {
+      //Q^n = [[Fn+1, Fn], [Fn, Fn-1]]
+      Q = power(Q,n-1);
+
+      //Q:{ _data:[[],[]], _size:[m, n], _datatype: string | number}
+      return Q['_data'][0][0];
+  }
+
+  return fibonacci(Q,n)
+
+}