






import timeit
class 					a_:



     """simple docstring"""



     def __init__(						self			:					List[str]       ,       lowerCAmelCase__			:					Dict)    ->					Any:

      """simple docstring"""
      if isinstance(lowercase_       ,       lowercase_):  # Initializes a matrix identical to the one provided.
       SCREAMING_SNAKE_CASE							  =						arg
       SCREAMING_SNAKE_CASE							  =						len(lowercase_)
      else:  # Initializes a square matrix of the given size and set values to zero.
       SCREAMING_SNAKE_CASE							  =						arg
       SCREAMING_SNAKE_CASE							  =						[[0 for _ in range(self.n)] for _ in range(self.n)]





     def __mul__(						self			:					str       ,       lowerCAmelCase__			:					Dict)    ->					Dict:

      """simple docstring"""
      SCREAMING_SNAKE_CASE							  =						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 		A_			(		lowercase_					,       lowercase_	)							->int:







 """simple docstring"""

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





def 		A_			(		lowercase_					,       lowercase_					,       lowercase_	)							->Dict:







 """simple docstring"""

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





def 		A_			(		lowercase_					,       lowercase_					,       lowercase_	)							->List[str]:







 """simple docstring"""

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

 SCREAMING_SNAKE_CASE							  =						fa
 SCREAMING_SNAKE_CASE							  =						fa
 n -= 2

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

 return fn_a





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







 """simple docstring"""

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





def 		A_			(		)							->Any:







 """simple docstring"""

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





def 		A_			(		)							->Tuple:







 """simple docstring"""

 matrix_exponentiation_time()
 simple_fibonacci_time()


if __name__ == "__main__":
      main()












def 		A_			(		lowercase_	)							->int:







 """simple docstring"""

 if not isinstance(lowercase_					,       lowercase_	):
  SCREAMING_SNAKE_CASE							  =						f'''Input value of [number={number}] must be an integer'''
  raise TypeError(lowercase_	)
 if number < 1:
  raise ValueError('Input must be a positive integer'	)
 return number * (2 * number - 1)


if __name__ == "__main__":
      import doctest

      doctest.testmod()




