



import functools
from math import sqrt
from time import time

def 					lowerCAmelCase__  (							_SCREAMING_SNAKE_CASE    :     Union[str, Any]			,       *_SCREAMING_SNAKE_CASE    :     Tuple			,       **_SCREAMING_SNAKE_CASE    :     Any      ):
				"""simple docstring"""







				__a					       =						time()
				__a					       =						func(*_SCREAMING_SNAKE_CASE			,       **_SCREAMING_SNAKE_CASE      )
				__a					       =						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__  (							_SCREAMING_SNAKE_CASE    :     int      ):
				"""simple docstring"""







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

def 					lowerCAmelCase__  (							_SCREAMING_SNAKE_CASE    :     int      ):
				"""simple docstring"""







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

def 					lowerCAmelCase__  (							_SCREAMING_SNAKE_CASE    :     int      ):
				"""simple docstring"""







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

def 					lowerCAmelCase__  (							_SCREAMING_SNAKE_CASE    :     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.
				__a					       =						{0: 0, 1: 1, 2: 1}  # Prefilled cache

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

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

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

def 					lowerCAmelCase__  (							_SCREAMING_SNAKE_CASE    :     int      ):
				"""simple docstring"""







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


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





from typing import TYPE_CHECKING

from ...utils import OptionalDependencyNotAvailable, _LazyModule, is_tf_available, is_torch_available


lowerCamelCase__     =	{"""configuration_hubert""": ["""HUBERT_PRETRAINED_CONFIG_ARCHIVE_MAP""", """HubertConfig"""]}

try:
						if not is_torch_available():
												raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
						pass
else:
						lowerCamelCase__     =	[
						    """HUBERT_PRETRAINED_MODEL_ARCHIVE_LIST""",
						    """HubertForCTC""",
						    """HubertForSequenceClassification""",
						    """HubertModel""",
						    """HubertPreTrainedModel""",
						]


try:
						if not is_tf_available():
												raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
						pass
else:
						lowerCamelCase__     =	[
						    """TF_HUBERT_PRETRAINED_MODEL_ARCHIVE_LIST""",
						    """TFHubertForCTC""",
						    """TFHubertModel""",
						    """TFHubertPreTrainedModel""",
						]

if TYPE_CHECKING:
						from .configuration_hubert import HUBERT_PRETRAINED_CONFIG_ARCHIVE_MAP, HubertConfig

						try:
												if not is_torch_available():
																		raise OptionalDependencyNotAvailable()
						except OptionalDependencyNotAvailable:
												pass
						else:
												from .modeling_hubert import (
												    HUBERT_PRETRAINED_MODEL_ARCHIVE_LIST,
												    HubertForCTC,
												    HubertForSequenceClassification,
												    HubertModel,
												    HubertPreTrainedModel,
												)

						try:
												if not is_tf_available():
																		raise OptionalDependencyNotAvailable()
						except OptionalDependencyNotAvailable:
												pass
						else:
												from .modeling_tf_hubert import (
												    TF_HUBERT_PRETRAINED_MODEL_ARCHIVE_LIST,
												    TFHubertForCTC,
												    TFHubertModel,
												    TFHubertPreTrainedModel,
												)


else:
						import sys

						lowerCamelCase__     =	_LazyModule(__name__, globals()["""__file__"""], _import_structure, module_spec=__spec__)
