matrix.nth_fibonacci_using_matrix_exponentiation
================================================

.. py:module:: matrix.nth_fibonacci_using_matrix_exponentiation

.. autoapi-nested-parse::

   Implementation of finding nth fibonacci number using matrix exponentiation.
   Time Complexity is about O(log(n)*8), where 8 is the complexity of matrix
   multiplication of size 2 by 2.
   And on the other hand complexity of bruteforce solution is O(n).
   As we know
       f[n] = f[n-1] + f[n-1]
   Converting to matrix,
       [f(n),f(n-1)] = [[1,1],[1,0]] * [f(n-1),f(n-2)]
   ->  [f(n),f(n-1)] = [[1,1],[1,0]]^2 * [f(n-2),f(n-3)]
       ...
       ...
   ->  [f(n),f(n-1)] = [[1,1],[1,0]]^(n-1) * [f(1),f(0)]
   So we just need the n times multiplication of the matrix [1,1],[1,0]].
   We can decrease the n times multiplication by following the divide and conquer approach.



Functions
---------

.. autoapisummary::

   matrix.nth_fibonacci_using_matrix_exponentiation.identity
   matrix.nth_fibonacci_using_matrix_exponentiation.main
   matrix.nth_fibonacci_using_matrix_exponentiation.multiply
   matrix.nth_fibonacci_using_matrix_exponentiation.nth_fibonacci_bruteforce
   matrix.nth_fibonacci_using_matrix_exponentiation.nth_fibonacci_matrix


Module Contents
---------------

.. py:function:: identity(n: int) -> list[list[int]]

.. py:function:: main() -> None

.. py:function:: multiply(matrix_a: list[list[int]], matrix_b: list[list[int]]) -> list[list[int]]

.. py:function:: nth_fibonacci_bruteforce(n: int) -> int

   >>> nth_fibonacci_bruteforce(100)
   354224848179261915075
   >>> nth_fibonacci_bruteforce(-100)
   -100


.. py:function:: nth_fibonacci_matrix(n: int) -> int

   >>> nth_fibonacci_matrix(100)
   354224848179261915075
   >>> nth_fibonacci_matrix(-100)
   -100