Function FibonacciMatrixExpo

Maths/Fibonacci.js:161–191

(num)

}

const FibonacciMatrixExpo = (num) => {
  const isBigInt = typeof num === 'bigint'
  const ZERO = isBigInt ? 0n : 0
  const ONE = isBigInt ? 1n : 1
  // F(0) = 0, F(1) = 1
  // F(n) = F(n-1) + F(n-2)
  // Consider below matrix multiplication:

  // | F(n) |   |1  1|   |F(n-1)|
  // |      | = |    | * |      |
  // |F(n-1)|   |1  0|   |F(n-2)|

  // 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 (num === ZERO) return num

  const isNeg = num < 0
  if (isNeg) num *= -ONE

  const A = [
    [ONE, ONE],
    [ONE, ZERO]
  ]

  const poweredA = matrixExpo(A, num - ONE) // A raised to the power n-1
  let F = [[ONE], [ZERO]]
  F = matrixMultiply(poweredA, F)
  return F[0][0] * (isNeg ? (-ONE) ** (num + ONE) : ONE)
}

/*
  Resource : https://math.hmc.edu/funfacts/fibonacci-number-formula/