
"""simple docstring"""





import functools
from math import sqrt
from time import time







def       __a	(						__lowerCamelCase,						*__lowerCamelCase,						**__lowerCamelCase    ):
   UpperCAmelCase_   :   Union[str, Any]     	=       time()
   UpperCAmelCase_   :   Dict     	=       func(*__lowerCamelCase,						**__lowerCamelCase    )
   UpperCAmelCase_   :   str     	=       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       __a	(						__lowerCamelCase    ):
   if n < 0:
      raise Exception("n is negative"    )
   if n == 0:
      return [0]
   UpperCAmelCase_   :   Optional[int]     	=       [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.
   UpperCAmelCase_   :   dict[int, int]     	=       {0: 0, 1: 1, 2: 1}  # Prefilled cache

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

      UpperCAmelCase_   :   List[Any]     	=       rec_fn_memoized(num - 1    ) + rec_fn_memoized(num - 2    )
      UpperCAmelCase_   :   List[Any]     	=       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 >= 1475:
      raise Exception("n is too large"    )
   UpperCAmelCase_   :   Any     	=       sqrt(5    )
   UpperCAmelCase_   :   Any     	=       (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)










'''simple docstring'''





from typing import TYPE_CHECKING

from ...utils import (
    OptionalDependencyNotAvailable,
    _LazyModule,
    is_flax_available,
    is_keras_nlp_available,
    is_tensorflow_text_available,
    is_tf_available,
    is_tokenizers_available,
    is_torch_available,
)


__A				:				Union[str, Any]					=		{
    """configuration_gpt2""": ["""GPT2_PRETRAINED_CONFIG_ARCHIVE_MAP""", """GPT2Config""", """GPT2OnnxConfig"""],
    """tokenization_gpt2""": ["""GPT2Tokenizer"""],
}

try:
 if not is_tokenizers_available():
  raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
 pass
else:
 __A				:				Tuple					=		["""GPT2TokenizerFast"""]

try:
 if not is_torch_available():
  raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
 pass
else:
 __A				:				Optional[int]					=		[
     """GPT2_PRETRAINED_MODEL_ARCHIVE_LIST""",
     """GPT2DoubleHeadsModel""",
     """GPT2ForQuestionAnswering""",
     """GPT2ForSequenceClassification""",
     """GPT2ForTokenClassification""",
     """GPT2LMHeadModel""",
     """GPT2Model""",
     """GPT2PreTrainedModel""",
     """load_tf_weights_in_gpt2""",
 ]

try:
 if not is_tf_available():
  raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
 pass
else:
 __A				:				Optional[Any]					=		[
     """TF_GPT2_PRETRAINED_MODEL_ARCHIVE_LIST""",
     """TFGPT2DoubleHeadsModel""",
     """TFGPT2ForSequenceClassification""",
     """TFGPT2LMHeadModel""",
     """TFGPT2MainLayer""",
     """TFGPT2Model""",
     """TFGPT2PreTrainedModel""",
 ]

try:
 if not is_keras_nlp_available():
  raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
 pass
else:
 __A				:				Any					=		["""TFGPT2Tokenizer"""]

try:
 if not is_flax_available():
  raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
 pass
else:
 __A				:				Tuple					=		["""FlaxGPT2LMHeadModel""", """FlaxGPT2Model""", """FlaxGPT2PreTrainedModel"""]

if TYPE_CHECKING:
 from .configuration_gpta import GPT2_PRETRAINED_CONFIG_ARCHIVE_MAP, GPTaConfig, GPTaOnnxConfig
 from .tokenization_gpta import GPTaTokenizer

 try:
  if not is_tokenizers_available():
   raise OptionalDependencyNotAvailable()
 except OptionalDependencyNotAvailable:
  pass
 else:
  from .tokenization_gpta_fast import GPTaTokenizerFast

 try:
  if not is_torch_available():
   raise OptionalDependencyNotAvailable()
 except OptionalDependencyNotAvailable:
  pass
 else:
  from .modeling_gpta import (
      GPT2_PRETRAINED_MODEL_ARCHIVE_LIST,
      GPTaDoubleHeadsModel,
      GPTaForQuestionAnswering,
      GPTaForSequenceClassification,
      GPTaForTokenClassification,
      GPTaLMHeadModel,
      GPTaModel,
      GPTaPreTrainedModel,
      load_tf_weights_in_gpta,
  )

 try:
  if not is_tf_available():
   raise OptionalDependencyNotAvailable()
 except OptionalDependencyNotAvailable:
  pass
 else:
  from .modeling_tf_gpta import (
      TF_GPT2_PRETRAINED_MODEL_ARCHIVE_LIST,
      TFGPTaDoubleHeadsModel,
      TFGPTaForSequenceClassification,
      TFGPTaLMHeadModel,
      TFGPTaMainLayer,
      TFGPTaModel,
      TFGPTaPreTrainedModel,
  )

 try:
  if not is_keras_nlp_available():
   raise OptionalDependencyNotAvailable()
 except OptionalDependencyNotAvailable:
  pass
 else:
  from .tokenization_gpta_tf import TFGPTaTokenizer

 try:
  if not is_flax_available():
   raise OptionalDependencyNotAvailable()
 except OptionalDependencyNotAvailable:
  pass
 else:
  from .modeling_flax_gpta import FlaxGPTaLMHeadModel, FlaxGPTaModel, FlaxGPTaPreTrainedModel

else:
 import sys

 __A				:				Tuple					=		_LazyModule(__name__, globals()["""__file__"""], _import_structure, module_spec=__spec__)

