Add extra testcases for Fibonacci and improve code (TheAlgorithms#544)

rahul1995 · web-flow · commit 8b1e32eb7702 · 2020-12-20T22:24:02.000+05:30
* Add extra testcases for Fibonacci and improve code
* Fix typos in Fibonacci.js
diff --git a/Maths/Fibonacci.js b/Maths/Fibonacci.js
@@ -102,14 +102,17 @@ const matrixMultiply = (A, B) => {
   return C
 }
 
+/**
+ * Computes A raised to the power n i.e. pow(A, n) where A is a square matrix
+ * @param {*} A the square matrix
+ * @param {*} n the exponent
+ */
 // A is a square matrix
 const matrixExpo = (A, n) => {
   A = copyMatrix(A)
-  if (n === 0) return Identity(A.length) // Identity matrix
-  if (n === 1) return A
 
   // Just like Binary exponentiation mentioned in ./BinaryExponentiationIterative.js
-  let result = Identity(A.length)
+  let result = Identity(A.length) // Identity matrix
   while (n > 0) {
     if (n % 2 !== 0) result = matrixMultiply(result, A)
     n = Math.floor(n / 2)
@@ -127,15 +130,17 @@ const FibonacciMatrixExpo = (n) => {
   // |      | = |    | * |      |
   // |F(n-1)|   |1  0|   |F(n-2)|
 
-  // F(n, n-1) = pow(A, n-1) * F(1, 0)
+  // Let's rewrite it as F(n, n-1) = A * F(n-1, n-2)
+  // or                  F(n, n-1) = A * A * F(n-2, n-3)
+  // or                  F(n, n-1) = pow(A, n-1) * F(1, 0)
 
   if (n === 0) return 0
 
   const A = [
     [1, 1],
     [1, 0]
   ]
-  const poweredA = matrixExpo(A, n - 1) // A raise to the power n
+  const poweredA = matrixExpo(A, n - 1) // A raised to the power n-1
   let F = [
     [1],
     [0]
diff --git a/Maths/test/Fibonacci.test.js b/Maths/test/Fibonacci.test.js
@@ -30,6 +30,11 @@ describe('Fibonanci', () => {
   })
 
   it('should return number for FibonnaciMatrixExpo', () => {
+    expect(FibonacciMatrixExpo(0)).toBe(0)
+    expect(FibonacciMatrixExpo(1)).toBe(1)
+    expect(FibonacciMatrixExpo(2)).toBe(1)
+    expect(FibonacciMatrixExpo(3)).toBe(2)
+    expect(FibonacciMatrixExpo(4)).toBe(3)
     expect(FibonacciMatrixExpo(5)).toBe(5)
   })
 })
