



'''simple docstring'''





import functools
from math import sqrt
from time import time
def 		_a   (  lowerCamelCase_					,						*lowerCamelCase_					,						**lowerCamelCase_							):
   snake_case   :							List[str]						  =time()
   snake_case   :							str						  =func(*lowerCamelCase_					,						**lowerCamelCase_							)
   snake_case   :							Dict						  =time()
   if int(end - start							) > 0:
      print(F'''{func.__name__} runtime: {(end - start):0.4f} s'''							)
   else:
      print(F'''{func.__name__} runtime: {(end - start) * 10_00:0.4f} ms'''							)
   return output
def 		_a   (  lowerCamelCase_							):
   if n < 0:
      raise Exception('''n is negative'''							)
   if n == 0:
      return [0]
   snake_case   :							List[str]						  =[0, 1]
   for _ in range(n - 1							):
      fib.append(fib[-1] + fib[-2]							)
   return fib
def 		_a   (  lowerCamelCase_							):

   def fib_recursive_term(lowerCamelCase_							) -> int:
      if i < 0:
         raise Exception('''n is negative'''							)
      if i < 2:
         return i
      return fib_recursive_term(i - 1							) + fib_recursive_term(i - 2							)

   if n < 0:
      raise Exception('''n is negative'''							)
   return [fib_recursive_term(lowerCamelCase_							) for i in range(n + 1							)]
def 		_a   (  lowerCamelCase_							):

   @functools.cache
   def fib_recursive_term(lowerCamelCase_							) -> int:
      if i < 0:
         raise Exception('''n is negative'''							)
      if i < 2:
         return i
      return fib_recursive_term(i - 1							) + fib_recursive_term(i - 2							)

   if n < 0:
      raise Exception('''n is negative'''							)
   return [fib_recursive_term(lowerCamelCase_							) for i in range(n + 1							)]
def 		_a   (  lowerCamelCase_							):
   if n < 0:
      raise Exception('''n is negative'''							)
   # Cache must be outside recursuive function
   # other it will reset every time it calls itself.
   snake_case   :							dict[int, int]						  ={0: 0, 1: 1, 2: 1}  # Prefilled cache

   def rec_fn_memoized(lowerCamelCase_							) -> int:
      if num in cache:
         return cache[num]

      snake_case   :							int						  =rec_fn_memoized(num - 1							) + rec_fn_memoized(num - 2							)
      snake_case   :							List[str]						  =value
      return value

   return [rec_fn_memoized(lowerCamelCase_							) for i in range(n + 1							)]
def 		_a   (  lowerCamelCase_							):
   if n < 0:
      raise Exception('''n is negative'''							)
   if n >= 14_75:
      raise Exception('''n is too large'''							)
   snake_case   :							Optional[int]						  =sqrt(5							)
   snake_case   :							List[Any]						  =(1 + sqrt_a) / 2
   return [round(phi**i / sqrt_a							) for i in range(n + 1							)]


if __name__ == "__main__":
      A			:   int			=      30
      time_func(fib_iterative, num)
      time_func(fib_recursive, num)  # Around 3s runtime
      time_func(fib_recursive_cached, num)  # Around 0ms runtime
      time_func(fib_memoization, num)
      time_func(fib_binet, num)










'''simple docstring'''





def 		_a   (  lowerCamelCase_							):
   return "".join(chr(ord(lowerCamelCase_							) + 32							) if '''A''' <= char <= '''Z''' else char for char in word							)


if __name__ == "__main__":
      from doctest import testmod

      testmod()





