

"""simple docstring"""




import functools
from math import sqrt
from time import time

def 		A    (       snake_case__						,			*snake_case__						,			**snake_case__      ):




   '''simple docstring'''


   SCREAMING_SNAKE_CASE__									= time()
   SCREAMING_SNAKE_CASE__									= func(*snake_case__						,			**snake_case__      )
   SCREAMING_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) * 10_00:0.4f} ms"""      )
   return output

def 		A    (       snake_case__      ):




   '''simple docstring'''


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

def 		A    (       snake_case__      ):




   '''simple docstring'''


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

def 		A    (       snake_case__      ):




   '''simple docstring'''


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

def 		A    (       snake_case__      ):




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

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

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

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

def 		A    (       snake_case__      ):




   '''simple docstring'''


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


if __name__ == "__main__":
      A_							:     Dict     =	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"""




class 				lowerCamelCase  :

			def __init__(   self			:  Dict    )				->      None:
						SCREAMING_SNAKE_CASE__									= [0, 1]





			def    SCREAMING_SNAKE_CASE			(   self			:  Optional[int]      ,			__UpperCAmelCase			:  int    )				->      list:
						if (difference := index - (len(self.sequence    ) - 2)) >= 1:
									for _ in range(__UpperCAmelCase    ):
												self.sequence.append(self.sequence[-1] + self.sequence[-2]    )
						return self.sequence[:index]

def 		A    (       ):




			'''simple docstring'''


			print(
			    """Fibonacci Series Using Dynamic Programming\n"""						,			"""Enter the index of the Fibonacci number you want to calculate """						,			"""in the prompt below. (To exit enter exit or Ctrl-C)\n"""						,			sep=""""""						,			)
			SCREAMING_SNAKE_CASE__									= Fibonacci()

			while True:
						SCREAMING_SNAKE_CASE__									= input(""">> """      )
						if prompt in {"exit", "quit"}:
									break

						try:
									SCREAMING_SNAKE_CASE__									= int(snake_case__      )
						except ValueError:
									print("""Enter a number or 'exit'"""      )
									continue

						print(fibonacci.get(snake_case__      )      )


if __name__ == "__main__":
						main()


