'''simple docstring'''


import functools
from math import sqrt
from time import time


def    _lowerCamelCase       ( lowerCamelCase_   :				Optional[int]      ,	*lowerCamelCase_   :				List[str]      ,	**lowerCamelCase_   :				int  ):



     """simple docstring"""





     UpperCAmelCase_				:  List[str]  = time()
     UpperCAmelCase_				:  Dict  = func(*_UpperCamelCase      ,	**_UpperCamelCase  )
     UpperCAmelCase_				:  int  = time()
     if int(end - start  ) > 0:
          print(F'''{func.__name__} runtime: {(end - start):0.4f} s'''  )
     else:
          print(F'''{func.__name__} runtime: {(end - start) * 1000:0.4f} ms'''  )
     return output


def    _lowerCamelCase       ( lowerCamelCase_   :				List[Any]  ):



     """simple docstring"""





     if n < 0:
          raise Exception('n is negative'  )
     if n == 0:
          return [0]
     UpperCAmelCase_				:  Tuple  = [0, 1]
     for _ in range(n - 1  ):
          fib.append(fib[-1] + fib[-2]  )
     return fib


def    _lowerCamelCase       ( lowerCamelCase_   :				str  ):



     """simple docstring"""





     def fib_recursive_term(lowerCamelCase_   :				Dict  ) -> 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(_UpperCamelCase  ) for i in range(n + 1  )]


def    _lowerCamelCase       ( lowerCamelCase_   :				Optional[int]  ):



     """simple docstring"""





     @functools.cache
     def fib_recursive_term(lowerCamelCase_   :				List[Any]  ) -> 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(_UpperCamelCase  ) for i in range(n + 1  )]


def    _lowerCamelCase       ( lowerCamelCase_   :				Tuple  ):



     """simple docstring"""





     if n < 0:
          raise Exception('n is negative'  )
     # Cache must be outside recursuive function
     # other it will reset every time it calls itself.
     UpperCAmelCase_				:  List[str]  = {0: 0, 1: 1, 2: 1}  # Prefilled cache

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

          UpperCAmelCase_				:  List[Any]  = rec_fn_memoized(num - 1  ) + rec_fn_memoized(num - 2  )
          UpperCAmelCase_				:  Optional[Any]  = value
          return value

     return [rec_fn_memoized(_UpperCamelCase  ) for i in range(n + 1  )]


def    _lowerCamelCase       ( lowerCamelCase_   :				str  ):



     """simple docstring"""





     if n < 0:
          raise Exception('n is negative'  )
     if n >= 1475:
          raise Exception('n is too large'  )
     UpperCAmelCase_				:  str  = sqrt(5  )
     UpperCAmelCase_				:  str  = (1 + sqrt_a) / 2
     return [round(phi**i / sqrt_a  ) for i in range(n + 1  )]


if __name__ == "__main__":
 snake_case__	:     List[Any]      =    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)









import functools
from math import sqrt
from time import time



def  snake_case_(_UpperCamelCase					,			*_UpperCamelCase					,			**_UpperCamelCase	)				->      str:



  """simple docstring"""






  _snake_case		=				time()
  _snake_case		=				func(*_UpperCamelCase					,			**_UpperCamelCase	)
  _snake_case		=				time()
  if int(end - start	) > 0:
    print(F"""{func.__name__} runtime: {(end - start):0.4f} s"""	)
  else:
    print(F"""{func.__name__} runtime: {(end - start) * 1_000:0.4f} ms"""	)
  return output



def  snake_case_(_UpperCamelCase	)				->      list[int]:



  """simple docstring"""






  if n < 0:
    raise Exception('''n is negative'''	)
  if n == 0:
    return [0]
  _snake_case		=				[0, 1]
  for _ in range(n - 1	):
    fib.append(fib[-1] + fib[-2]	)
  return fib



def  snake_case_(_UpperCamelCase	)				->      list[int]:



  """simple docstring"""






  def fib_recursive_term(_UpperCamelCase	) -> 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(_UpperCamelCase	) for i in range(n + 1	)]



def  snake_case_(_UpperCamelCase	)				->      list[int]:



  """simple docstring"""






  @functools.cache
  def fib_recursive_term(_UpperCamelCase	) -> 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(_UpperCamelCase	) for i in range(n + 1	)]



def  snake_case_(_UpperCamelCase	)				->      list[int]:



  """simple docstring"""






  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		=				{0: 0, 1: 1, 2: 1}  # Prefilled cache

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

    _snake_case		=				rec_fn_memoized(num - 1	) + rec_fn_memoized(num - 2	)
    _snake_case		=				value
    return value

  return [rec_fn_memoized(_UpperCamelCase	) for i in range(n + 1	)]



def  snake_case_(_UpperCamelCase	)				->      list[int]:



  """simple docstring"""






  if n < 0:
    raise Exception('''n is negative'''	)
  if n >= 1_475:
    raise Exception('''n is too large'''	)
  _snake_case		=				sqrt(5	)
  _snake_case		=				(1 + sqrt_a) / 2
  return [round(phi**i / sqrt_a	) for i in range(n + 1	)]


if __name__ == "__main__":
 __A     						=      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)

