
"""simple docstring"""

import timeit
class        _UpperCAmelCase							:




      def __init__(							self				,    lowercase_							)  ->   Any:
          if isinstance(lowercase_				,    lowercase_							):  # Initializes a matrix identical to the one provided.
              UpperCAmelCase       =   arg
              UpperCAmelCase       =   len(lowercase_							)
          else:  # Initializes a square matrix of the given size and set values to zero.
              UpperCAmelCase       =   arg
              UpperCAmelCase       =   [[0 for _ in range(self.n							)] for _ in range(self.n							)]




      def __mul__(							self				,    lowercase_							)  ->   Dict:
          UpperCAmelCase       =   Matrix(self.n							)
          for i in range(self.n							):
              for j in range(self.n							):
                  for k in range(self.n							):
                      matrix.t[i][j] += self.t[i][k] * b.t[k][j]
          return matrix




def       lowercase__  (   lowerCAmelCase			:   List[str]	,			lowerCAmelCase			:   Optional[Any]	)	-> int:






    """simple docstring"""




    UpperCAmelCase       =   Matrix([[1, 0], [0, 1]]	)
    while b > 0:
        if b & 1:
            matrix *= a
        a *= a
        b >>= 1
    return matrix




def       lowercase__  (   lowerCAmelCase			:   Tuple	,			lowerCAmelCase			:   int	,			lowerCAmelCase			:   Optional[Any]	)	-> Dict:






    """simple docstring"""




    if n == 1:
        return fa
    elif n == 2:
        return fa
    UpperCAmelCase       =   Matrix([[1, 1], [1, 0]]	)
    UpperCAmelCase       =   modular_exponentiation(lowerCAmelCase	,			n - 2	)
    return fa * matrix.t[0][0] + fa * matrix.t[0][1]




def       lowercase__  (   lowerCAmelCase			:   Optional[int]	,			lowerCAmelCase			:   List[Any]	,			lowerCAmelCase			:   Optional[Any]	)	-> List[str]:






    """simple docstring"""




    if n == 1:
        return fa
    elif n == 2:
        return fa

    UpperCAmelCase       =   fa
    UpperCAmelCase       =   fa
    n -= 2

    while n > 0:
        UpperCAmelCase     ,							UpperCAmelCase       =   fn_a + fn_a, fn_a
        n -= 1

    return fn_a




def       lowercase__  (   )	-> Union[str, Any]:






    """simple docstring"""




    UpperCAmelCase       =   '\nfrom random import randint\nfrom __main__ import fibonacci_with_matrix_exponentiation\n'
    UpperCAmelCase       =   'fibonacci_with_matrix_exponentiation(randint(1,70000), 1, 1)'
    UpperCAmelCase       =   timeit.timeit(setup=lowerCAmelCase	,			stmt=lowerCAmelCase	,			number=100	)
    print('With matrix exponentiation the average execution time is '	,			exec_time / 100	)
    return exec_time




def       lowercase__  (   )	-> Any:






    """simple docstring"""




    UpperCAmelCase       =   '\nfrom random import randint\nfrom __main__ import simple_fibonacci\n'
    UpperCAmelCase       =   'simple_fibonacci(randint(1,70000), 1, 1)'
    UpperCAmelCase       =   timeit.timeit(setup=lowerCAmelCase	,			stmt=lowerCAmelCase	,			number=100	)
    print(
        'Without matrix exponentiation the average execution time is '	,			exec_time / 100	)
    return exec_time




def       lowercase__  (   )	-> Tuple:






    """simple docstring"""




    matrix_exponentiation_time()
    simple_fibonacci_time()


if __name__ == "__main__":
   main()





"""simple docstring"""

from __future__ import annotations

SCREAMING_SNAKE_CASE_         =  '''Alexander Joslin'''




def       lowercase__  (   lowerCAmelCase			:   int	)	-> int:






    """simple docstring"""




    if number <= 0:
        UpperCAmelCase       =   F"n must be greater than 0. Got n = {number}"
        raise ValueError(lowerCAmelCase	)

    UpperCAmelCase       =   [number + 1] * (number + 1)

    # starting position
    UpperCAmelCase       =   0
    for i in range(1	,			lowerCAmelCase	):
        UpperCAmelCase       =   min(table[i + 1]	,			table[i] + 1	)
        # check if out of bounds
        if i * 2 <= number:
            UpperCAmelCase       =   min(table[i * 2]	,			table[i] + 1	)
        # check if out of bounds
        if i * 3 <= number:
            UpperCAmelCase       =   min(table[i * 3]	,			table[i] + 1	)
    return table[number]


if __name__ == "__main__":
   import doctest

   doctest.testmod()



