




'''simple docstring'''



from typing import TYPE_CHECKING

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


UpperCAmelCase_				:     Optional[Any]     			=						{
    '''configuration_openai''': ['''OPENAI_GPT_PRETRAINED_CONFIG_ARCHIVE_MAP''', '''OpenAIGPTConfig'''],
    '''tokenization_openai''': ['''OpenAIGPTTokenizer'''],
}

try:
     if not is_tokenizers_available():
          raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
     pass
else:
     UpperCAmelCase_				:     List[Any]     			=						['''OpenAIGPTTokenizerFast''']

try:
     if not is_torch_available():
          raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
     pass
else:
     UpperCAmelCase_				:     Dict     			=						[
         '''OPENAI_GPT_PRETRAINED_MODEL_ARCHIVE_LIST''',
         '''OpenAIGPTDoubleHeadsModel''',
         '''OpenAIGPTForSequenceClassification''',
         '''OpenAIGPTLMHeadModel''',
         '''OpenAIGPTModel''',
         '''OpenAIGPTPreTrainedModel''',
         '''load_tf_weights_in_openai_gpt''',
     ]

try:
     if not is_tf_available():
          raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
     pass
else:
     UpperCAmelCase_				:     List[str]     			=						[
         '''TF_OPENAI_GPT_PRETRAINED_MODEL_ARCHIVE_LIST''',
         '''TFOpenAIGPTDoubleHeadsModel''',
         '''TFOpenAIGPTForSequenceClassification''',
         '''TFOpenAIGPTLMHeadModel''',
         '''TFOpenAIGPTMainLayer''',
         '''TFOpenAIGPTModel''',
         '''TFOpenAIGPTPreTrainedModel''',
     ]


if TYPE_CHECKING:
     from .configuration_openai import OPENAI_GPT_PRETRAINED_CONFIG_ARCHIVE_MAP, OpenAIGPTConfig
     from .tokenization_openai import OpenAIGPTTokenizer

     try:
          if not is_tokenizers_available():
               raise OptionalDependencyNotAvailable()
     except OptionalDependencyNotAvailable:
          pass
     else:
          from .tokenization_openai_fast import OpenAIGPTTokenizerFast

     try:
          if not is_torch_available():
               raise OptionalDependencyNotAvailable()
     except OptionalDependencyNotAvailable:
          pass
     else:
          from .modeling_openai import (
              OPENAI_GPT_PRETRAINED_MODEL_ARCHIVE_LIST,
              OpenAIGPTDoubleHeadsModel,
              OpenAIGPTForSequenceClassification,
              OpenAIGPTLMHeadModel,
              OpenAIGPTModel,
              OpenAIGPTPreTrainedModel,
              load_tf_weights_in_openai_gpt,
          )

     try:
          if not is_tf_available():
               raise OptionalDependencyNotAvailable()
     except OptionalDependencyNotAvailable:
          pass
     else:
          from .modeling_tf_openai import (
              TF_OPENAI_GPT_PRETRAINED_MODEL_ARCHIVE_LIST,
              TFOpenAIGPTDoubleHeadsModel,
              TFOpenAIGPTForSequenceClassification,
              TFOpenAIGPTLMHeadModel,
              TFOpenAIGPTMainLayer,
              TFOpenAIGPTModel,
              TFOpenAIGPTPreTrainedModel,
          )

else:
     import sys

     UpperCAmelCase_				:     Union[str, Any]     			=						_LazyModule(__name__, globals()['''__file__'''], _import_structure, module_spec=__spec__)












'''simple docstring'''



def 	_UpperCamelCase       (_lowerCamelCase							:   list[list[int]]      ,		_lowerCamelCase							:   list[list[int]]		)->      list[list[int]]:




     '''simple docstring'''





     __snake_case			    =     []
     __snake_case			    =     len(_lowerCamelCase		)
     for i in range(_lowerCamelCase		):
          __snake_case			    =     []
          for j in range(_lowerCamelCase		):
               __snake_case			    =     0
               for k in range(_lowerCamelCase		):
                    __snake_case			    =     val + matrix_a[i][k] * matrix_b[k][j]
               list_a.append(_lowerCamelCase		)
          matrix_c.append(_lowerCamelCase		)
     return matrix_c







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




     '''simple docstring'''





     return [[int(row == column		) for column in range(_lowerCamelCase		)] for row in range(_lowerCamelCase		)]







def 	_UpperCamelCase       (_lowerCamelCase							:   int		)->      int:




     '''simple docstring'''





     if n <= 1:
          return n
     __snake_case			    =     identity(2		)
     __snake_case			    =     [[1, 1], [1, 0]]
     __snake_case			    =     n - 1
     while n > 0:
          if n % 2 == 1:
               __snake_case			    =     multiply(_lowerCamelCase      ,		_lowerCamelCase		)
          __snake_case			    =     multiply(_lowerCamelCase      ,		_lowerCamelCase		)
          __snake_case			    =     int(n / 2		)
     return res_matrix[0][0]







def 	_UpperCamelCase       (_lowerCamelCase							:   int		)->      int:




     '''simple docstring'''





     if n <= 1:
          return n
     __snake_case			    =     0
     __snake_case			    =     1
     for _ in range(2      ,		n + 1		):
          __snake_case    ,			__snake_case			    =     fiba, fiba + fiba
     return fiba







def 	_UpperCamelCase       ()->      None:




     '''simple docstring'''





     for ordinal in "0th 1st 2nd 3rd 10th 100th 1000th".split():
          __snake_case			    =     int(''''''.join(c for c in ordinal if c in '''0123456789'''		)		)  # 1000th --> 1000
          print(
              f'''{ordinal} fibonacci number using matrix exponentiation is '''
              f'''{nth_fibonacci_matrix(_lowerCamelCase		)} and using bruteforce is '''
              f'''{nth_fibonacci_bruteforce(_lowerCamelCase		)}\n'''		)
     # from timeit import timeit
     # print(timeit("nth_fibonacci_matrix(1000000)",
     #              "from main import nth_fibonacci_matrix", number=5))
     # print(timeit("nth_fibonacci_bruteforce(1000000)",
     #              "from main import nth_fibonacci_bruteforce", number=5))
     # 2.3342058970001744
     # 57.256506615000035


if __name__ == "__main__":
     import doctest

     doctest.testmod()
     main()






