fib(n: int) -> int
This function calculates the n-th Fibonacci number efficiently using matrix exponentiation.
\( \begin{array}{l} f(0) = 0 \\ f(1) = 1 \\ \text{For } n \geq 2 \\ f(n) = f(n-1) + f(n-2) \end{array} \)
strassen_mult(x: list[list[int]], y: list[list[int]]) -> list[list[int]]
Multiplies 2 by 2 matricies using the Strassen algorithm which is faster than regular matrix multiplication by decomposing the matrix to use more addition operations and fewer multiplication operations.
\( \begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \\ \end{bmatrix} \times \begin{bmatrix} b_{11} & b_{12} \\ b_{21} & b_{22} \\ \end{bmatrix} = \begin{bmatrix} c_{11} & c_{12} \\ c_{21} & c_{22} \\ \end{bmatrix} \)
matrix_exp(m: list[list[int]], n: int) -> list[list[int]]
Calculates the exponentiation of a matrix. This is useful for the Fibonacci function as due to a linear recurrence relation, the following matrix exponentiation results in calculating the Fibonacci numbers.
\( \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix}^n = \begin{bmatrix} \text{fib}(n+1) & \text{fib}(n) \\ \text{fib}(n) & \text{fib}(n-1) \\ \end{bmatrix} \)
This results in an algorithm with a \( O(\log(n)) \) time complexity with the laws of exponents.
\( x^n = \begin{cases} x(x^2)^{n-1/2} & \text{if } n \text{ is odd} \\ (x^2)^{n/2} & \text{if } n \text{ is even} \end{cases} \)