'''simple docstring'''

import json
import os
import re
import unicodedata
from typing import Dict, List, Optional, Tuple

from ...tokenization_utils import PreTrainedTokenizer
from ...utils import logging


_A      :				Optional[int] 				=    logging.get_logger(__name__)

_A      :				int 				=    {
    '''src_vocab_file''': '''vocab-src.json''',
    '''tgt_vocab_file''': '''vocab-tgt.json''',
    '''merges_file''': '''merges.txt''',
}

_A      :				Dict 				=    {
    '''src_vocab_file''': {
        '''stas/tiny-wmt19-en-de''': '''https://huggingface.co/stas/tiny-wmt19-en-de/resolve/main/vocab-src.json'''
    },
    '''tgt_vocab_file''': {
        '''stas/tiny-wmt19-en-de''': '''https://huggingface.co/stas/tiny-wmt19-en-de/resolve/main/vocab-tgt.json'''
    },
    '''merges_file''': {'''stas/tiny-wmt19-en-de''': '''https://huggingface.co/stas/tiny-wmt19-en-de/resolve/main/merges.txt'''},
}

_A      :				List[Any] 				=    {'''stas/tiny-wmt19-en-de''': 1024}
_A      :				Optional[Any] 				=    {
    '''stas/tiny-wmt19-en-de''': {
        '''langs''': ['''en''', '''de'''],
        '''model_max_length''': 1024,
        '''special_tokens_map_file''': None,
        '''full_tokenizer_file''': None,
    }
}







def 					UpperCamelCase_						( snake_case_	:	Tuple				) ->					Optional[int]:






 '''simple docstring'''

 __lowerCAmelCase    							=						set()
 __lowerCAmelCase    							=						word[0]
 for char in word[1:]:
  pairs.add((prev_char, char)				)
  __lowerCAmelCase    							=						char
 return pairs







def 					UpperCamelCase_						( snake_case_	:	Optional[Any]				) ->					List[str]:






 '''simple docstring'''

 __lowerCAmelCase    							=						text.replace("""，"""						,		""","""				)
 __lowerCAmelCase    							=						re.sub(r"""。\s*"""						,		""". """						,		snake_case_				)
 __lowerCAmelCase    							=						text.replace("""、"""						,		""","""				)
 __lowerCAmelCase    							=						text.replace("""”"""						,		"""\""""				)
 __lowerCAmelCase    							=						text.replace("""“"""						,		"""\""""				)
 __lowerCAmelCase    							=						text.replace("""∶"""						,		""":"""				)
 __lowerCAmelCase    							=						text.replace("""："""						,		""":"""				)
 __lowerCAmelCase    							=						text.replace("""？"""						,		"""?"""				)
 __lowerCAmelCase    							=						text.replace("""《"""						,		"""\""""				)
 __lowerCAmelCase    							=						text.replace("""》"""						,		"""\""""				)
 __lowerCAmelCase    							=						text.replace("""）"""						,		""")"""				)
 __lowerCAmelCase    							=						text.replace("""！"""						,		"""!"""				)
 __lowerCAmelCase    							=						text.replace("""（"""						,		"""("""				)
 __lowerCAmelCase    							=						text.replace("""；"""						,		""";"""				)
 __lowerCAmelCase    							=						text.replace("""１"""						,		"""1"""				)
 __lowerCAmelCase    							=						text.replace("""」"""						,		"""\""""				)
 __lowerCAmelCase    							=						text.replace("""「"""						,		"""\""""				)
 __lowerCAmelCase    							=						text.replace("""０"""						,		"""0"""				)
 __lowerCAmelCase    							=						text.replace("""３"""						,		"""3"""				)
 __lowerCAmelCase    							=						text.replace("""２"""						,		"""2"""				)
 __lowerCAmelCase    							=						text.replace("""５"""						,		"""5"""				)
 __lowerCAmelCase    							=						text.replace("""６"""						,		"""6"""				)
 __lowerCAmelCase    							=						text.replace("""９"""						,		"""9"""				)
 __lowerCAmelCase    							=						text.replace("""７"""						,		"""7"""				)
 __lowerCAmelCase    							=						text.replace("""８"""						,		"""8"""				)
 __lowerCAmelCase    							=						text.replace("""４"""						,		"""4"""				)
 __lowerCAmelCase    							=						re.sub(r"""．\s*"""						,		""". """						,		snake_case_				)
 __lowerCAmelCase    							=						text.replace("""～"""						,		"""~"""				)
 __lowerCAmelCase    							=						text.replace("""’"""						,		"""'"""				)
 __lowerCAmelCase    							=						text.replace("""…"""						,		"""..."""				)
 __lowerCAmelCase    							=						text.replace("""━"""						,		"""-"""				)
 __lowerCAmelCase    							=						text.replace("""〈"""						,		"""<"""				)
 __lowerCAmelCase    							=						text.replace("""〉"""						,		""">"""				)
 __lowerCAmelCase    							=						text.replace("""【"""						,		"""["""				)
 __lowerCAmelCase    							=						text.replace("""】"""						,		"""]"""				)
 __lowerCAmelCase    							=						text.replace("""％"""						,		"""%"""				)
 return text







def 					UpperCamelCase_						( snake_case_	:	Union[str, Any]				) ->					Union[str, Any]:






 '''simple docstring'''

 __lowerCAmelCase    							=						[]
 for char in text:
  __lowerCAmelCase    							=						unicodedata.category(snake_case_				)
  if cat.startswith("""C"""				):
   continue
  output.append(snake_case_				)
 return "".join(snake_case_				)







class     _lowercase					(    UpperCAmelCase__      ):


 '''simple docstring'''






 _SCREAMING_SNAKE_CASE					:	List[Any]				     = VOCAB_FILES_NAMES
 _SCREAMING_SNAKE_CASE					:	str				     = PRETRAINED_VOCAB_FILES_MAP
 _SCREAMING_SNAKE_CASE					:	Dict				     = PRETRAINED_INIT_CONFIGURATION
 _SCREAMING_SNAKE_CASE					:	List[Any]				     = PRETRAINED_POSITIONAL_EMBEDDINGS_SIZES
 _SCREAMING_SNAKE_CASE					:	List[Any]				     = ["""input_ids""", """attention_mask"""]
 def __init__(				self       :     int				,	SCREAMING_SNAKE_CASE__       :     str=None				,	SCREAMING_SNAKE_CASE__       :     Union[str, Any]=None				,	SCREAMING_SNAKE_CASE__       :     int=None				,	SCREAMING_SNAKE_CASE__       :     Optional[int]=None				,	SCREAMING_SNAKE_CASE__       :     List[Any]=False				,	SCREAMING_SNAKE_CASE__       :     Optional[int]="<unk>"				,	SCREAMING_SNAKE_CASE__       :     Dict="<s>"				,	SCREAMING_SNAKE_CASE__       :     int="</s>"				,	SCREAMING_SNAKE_CASE__       :     Dict="<pad>"				,	**SCREAMING_SNAKE_CASE__       :     Any				,	)  ->   Optional[Any]:
  super().__init__(
      langs=SCREAMING_SNAKE_CASE__				,	src_vocab_file=SCREAMING_SNAKE_CASE__				,	tgt_vocab_file=SCREAMING_SNAKE_CASE__				,	merges_file=SCREAMING_SNAKE_CASE__				,	do_lower_case=SCREAMING_SNAKE_CASE__				,	unk_token=SCREAMING_SNAKE_CASE__				,	bos_token=SCREAMING_SNAKE_CASE__				,	sep_token=SCREAMING_SNAKE_CASE__				,	pad_token=SCREAMING_SNAKE_CASE__				,	**SCREAMING_SNAKE_CASE__				,	)

  try:
   import sacremoses
  except ImportError:
   raise ImportError(
       """You need to install sacremoses to use XLMTokenizer. """
       """See https://pypi.org/project/sacremoses/ for installation."""							)

  __lowerCAmelCase    							=						sacremoses

  __lowerCAmelCase    							=						src_vocab_file
  __lowerCAmelCase    							=						tgt_vocab_file
  __lowerCAmelCase    							=						merges_file
  __lowerCAmelCase    							=						do_lower_case

  # cache of sm.MosesPunctNormalizer instance
  __lowerCAmelCase    							=						{}
  # cache of sm.MosesTokenizer instance
  __lowerCAmelCase    							=						{}
  __lowerCAmelCase    							=						{}

  if langs and len(SCREAMING_SNAKE_CASE__							) == 2:
   __lowerCAmelCase							,	__lowerCAmelCase    							=						langs
  else:
   raise ValueError(
       f"""arg `langs` needs to be a list of 2 langs, e.g. ['en', 'ru'], but got {langs}. """
       """Usually that means that tokenizer can't find a mapping for the given model path """
       """in PRETRAINED_VOCAB_FILES_MAP, and other maps of this tokenizer."""							)

  with open(SCREAMING_SNAKE_CASE__				,	encoding="""utf-8"""							) as src_vocab_handle:
   __lowerCAmelCase    							=						json.load(SCREAMING_SNAKE_CASE__							)
  with open(SCREAMING_SNAKE_CASE__				,	encoding="""utf-8"""							) as tgt_vocab_handle:
   __lowerCAmelCase    							=						json.load(SCREAMING_SNAKE_CASE__							)
   __lowerCAmelCase    							=						{v: k for k, v in tgt_vocab.items()}
  with open(SCREAMING_SNAKE_CASE__				,	encoding="""utf-8"""							) as merges_handle:
   __lowerCAmelCase    							=						merges_handle.read().split("""\n"""							)[:-1]
  __lowerCAmelCase    							=						[tuple(merge.split()[:2]							) for merge in merges]
  __lowerCAmelCase    							=						dict(zip(SCREAMING_SNAKE_CASE__				,	range(len(SCREAMING_SNAKE_CASE__							)							)							)							)
  __lowerCAmelCase    							=						{}
 def a (				self       :     str							)  ->   Dict[str, int]:
  return self.get_src_vocab()
 @property
 def a (				self       :     str							)  ->   int:
  return self.src_vocab_size
 def a (				self       :     Any				,	SCREAMING_SNAKE_CASE__       :     Optional[Any]				,	SCREAMING_SNAKE_CASE__       :     Union[str, Any]							)  ->   int:
  if lang not in self.cache_moses_punct_normalizer:
   __lowerCAmelCase    							=						self.sm.MosesPunctNormalizer(lang=SCREAMING_SNAKE_CASE__							)
   __lowerCAmelCase    							=						punct_normalizer
  return self.cache_moses_punct_normalizer[lang].normalize(SCREAMING_SNAKE_CASE__							)
 def a (				self       :     List[Any]				,	SCREAMING_SNAKE_CASE__       :     Dict				,	SCREAMING_SNAKE_CASE__       :     Union[str, Any]							)  ->   Any:
  if lang not in self.cache_moses_tokenizer:
   __lowerCAmelCase    							=						self.sm.MosesTokenizer(lang=SCREAMING_SNAKE_CASE__							)
   __lowerCAmelCase    							=						moses_tokenizer
  return self.cache_moses_tokenizer[lang].tokenize(
      SCREAMING_SNAKE_CASE__				,	aggressive_dash_splits=SCREAMING_SNAKE_CASE__				,	return_str=SCREAMING_SNAKE_CASE__				,	escape=SCREAMING_SNAKE_CASE__							)
 def a (				self       :     Any				,	SCREAMING_SNAKE_CASE__       :     int				,	SCREAMING_SNAKE_CASE__       :     Union[str, Any]							)  ->   int:
  if lang not in self.cache_moses_detokenizer:
   __lowerCAmelCase    							=						self.sm.MosesDetokenizer(lang=SCREAMING_SNAKE_CASE__							)
   __lowerCAmelCase    							=						moses_detokenizer
  return self.cache_moses_detokenizer[lang].detokenize(SCREAMING_SNAKE_CASE__							)
 def a (				self       :     int				,	SCREAMING_SNAKE_CASE__       :     Any				,	SCREAMING_SNAKE_CASE__       :     Tuple							)  ->   List[str]:
  __lowerCAmelCase    							=						replace_unicode_punct(SCREAMING_SNAKE_CASE__							)
  __lowerCAmelCase    							=						self.moses_punct_norm(SCREAMING_SNAKE_CASE__				,	SCREAMING_SNAKE_CASE__							)
  __lowerCAmelCase    							=						remove_non_printing_char(SCREAMING_SNAKE_CASE__							)
  return text
 @property
 def a (				self       :     Any							)  ->   int:
  return len(self.encoder							)
 @property
 def a (				self       :     Optional[int]							)  ->   Optional[Any]:
  return len(self.decoder							)
 def a (				self       :     Optional[int]							)  ->   Optional[int]:
  return dict(self.encoder				,	**self.added_tokens_encoder							)
 def a (				self       :     int							)  ->   Tuple:
  return dict(self.decoder				,	**self.added_tokens_decoder							)
 def a (				self       :     Dict				,	SCREAMING_SNAKE_CASE__       :     Tuple							)  ->   Optional[Any]:
  __lowerCAmelCase    							=						tuple(token[:-1]							) + (token[-1] + """</w>""",)
  if token in self.cache:
   return self.cache[token]
  __lowerCAmelCase    							=						get_pairs(SCREAMING_SNAKE_CASE__							)

  if not pairs:
   return token + "</w>"

  while True:
   __lowerCAmelCase    							=						min(SCREAMING_SNAKE_CASE__				,	key=lambda SCREAMING_SNAKE_CASE__							: self.bpe_ranks.get(SCREAMING_SNAKE_CASE__				,	float("""inf"""							)							)							)
   if bigram not in self.bpe_ranks:
    break
   __lowerCAmelCase							,	__lowerCAmelCase    							=						bigram
   __lowerCAmelCase    							=						[]
   __lowerCAmelCase    							=						0
   while i < len(SCREAMING_SNAKE_CASE__							):
    try:
     __lowerCAmelCase    							=						word.index(SCREAMING_SNAKE_CASE__				,	SCREAMING_SNAKE_CASE__							)
    except ValueError:
     new_word.extend(word[i:]							)
     break
    else:
     new_word.extend(word[i:j]							)
     __lowerCAmelCase    							=						j

    if word[i] == first and i < len(SCREAMING_SNAKE_CASE__							) - 1 and word[i + 1] == second:
     new_word.append(first + second							)
     i += 2
    else:
     new_word.append(word[i]							)
     i += 1
   __lowerCAmelCase    							=						tuple(SCREAMING_SNAKE_CASE__							)
   __lowerCAmelCase    							=						new_word
   if len(SCREAMING_SNAKE_CASE__							) == 1:
    break
   else:
    __lowerCAmelCase    							=						get_pairs(SCREAMING_SNAKE_CASE__							)
  __lowerCAmelCase    							=						""" """.join(SCREAMING_SNAKE_CASE__							)
  if word == "\n  </w>":
   __lowerCAmelCase    							=						"""\n</w>"""
  __lowerCAmelCase    							=						word
  return word
 def a (				self       :     Optional[int]				,	SCREAMING_SNAKE_CASE__       :     Dict				,	SCREAMING_SNAKE_CASE__       :     Optional[Any]="en"				,	SCREAMING_SNAKE_CASE__       :     Union[str, Any]=False							)  ->   str:
  __lowerCAmelCase    							=						self.src_lang

  if self.do_lower_case:
   __lowerCAmelCase    							=						text.lower()

  if bypass_tokenizer:
   __lowerCAmelCase    							=						text.split()
  else:
   __lowerCAmelCase    							=						self.moses_pipeline(SCREAMING_SNAKE_CASE__				,	lang=SCREAMING_SNAKE_CASE__							)
   __lowerCAmelCase    							=						self.moses_tokenize(SCREAMING_SNAKE_CASE__				,	lang=SCREAMING_SNAKE_CASE__							)

  __lowerCAmelCase    							=						[]
  for token in text:
   if token:
    split_tokens.extend(list(self.bpe(SCREAMING_SNAKE_CASE__							).split(""" """							)							)							)

  return split_tokens
 def a (				self       :     Union[str, Any]				,	SCREAMING_SNAKE_CASE__       :     Tuple							)  ->   Optional[Any]:
  return self.encoder.get(SCREAMING_SNAKE_CASE__				,	self.encoder.get(self.unk_token							)							)
 def a (				self       :     Optional[Any]				,	SCREAMING_SNAKE_CASE__       :     List[Any]							)  ->   Any:
  return self.decoder.get(SCREAMING_SNAKE_CASE__				,	self.unk_token							)
 def a (				self       :     int				,	SCREAMING_SNAKE_CASE__       :     Union[str, Any]							)  ->   int:
  __lowerCAmelCase    							=						[t.replace(""" """				,	""""""							).replace("""</w>"""				,	""" """							) for t in tokens]
  __lowerCAmelCase    							=						"""""".join(SCREAMING_SNAKE_CASE__							).split()
  # detokenize
  __lowerCAmelCase    							=						self.moses_detokenize(SCREAMING_SNAKE_CASE__				,	self.tgt_lang							)
  return text
 def a (				self       :     Dict				,	SCREAMING_SNAKE_CASE__       :     List[int]				,	SCREAMING_SNAKE_CASE__       :     Optional[List[int]] = None							)  ->   List[int]:
  __lowerCAmelCase    							=						[self.sep_token_id]

  # no bos used in fairseq
  if token_ids_a is None:
   return token_ids_a + sep
  return token_ids_a + sep + token_ids_a + sep
 def a (				self       :     Optional[Any]				,	SCREAMING_SNAKE_CASE__       :     List[int]				,	SCREAMING_SNAKE_CASE__       :     Optional[List[int]] = None				,	SCREAMING_SNAKE_CASE__       :     bool = False							)  ->   List[int]:

  if already_has_special_tokens:
   return super().get_special_tokens_mask(
       token_ids_a=SCREAMING_SNAKE_CASE__				,	token_ids_a=SCREAMING_SNAKE_CASE__				,	already_has_special_tokens=SCREAMING_SNAKE_CASE__							)
  # no bos used in fairseq
  if token_ids_a is not None:
   return ([0] * len(SCREAMING_SNAKE_CASE__							)) + [1] + ([0] * len(SCREAMING_SNAKE_CASE__							)) + [1]
  return ([0] * len(SCREAMING_SNAKE_CASE__							)) + [1]
 def a (				self       :     Tuple				,	SCREAMING_SNAKE_CASE__       :     List[int]				,	SCREAMING_SNAKE_CASE__       :     Optional[List[int]] = None							)  ->   List[int]:
  __lowerCAmelCase    							=						[self.sep_token_id]

  # no bos used in fairseq
  if token_ids_a is None:
   return len(token_ids_a + sep							) * [0]
  return len(token_ids_a + sep							) * [0] + len(token_ids_a + sep							) * [1]
 def a (				self       :     List[str]				,	SCREAMING_SNAKE_CASE__       :     str				,	SCREAMING_SNAKE_CASE__       :     Optional[str] = None							)  ->   Tuple[str]:
  if not os.path.isdir(SCREAMING_SNAKE_CASE__							):
   logger.error(f"""Vocabulary path ({save_directory}) should be a directory"""							)
   return

  __lowerCAmelCase    							=						os.path.join(
      SCREAMING_SNAKE_CASE__				,	(filename_prefix + """-""" if filename_prefix else """""") + VOCAB_FILES_NAMES["""src_vocab_file"""]							)
  __lowerCAmelCase    							=						os.path.join(
      SCREAMING_SNAKE_CASE__				,	(filename_prefix + """-""" if filename_prefix else """""") + VOCAB_FILES_NAMES["""tgt_vocab_file"""]							)
  __lowerCAmelCase    							=						os.path.join(
      SCREAMING_SNAKE_CASE__				,	(filename_prefix + """-""" if filename_prefix else """""") + VOCAB_FILES_NAMES["""merges_file"""]							)

  with open(SCREAMING_SNAKE_CASE__				,	"""w"""				,	encoding="""utf-8"""							) as f:
   f.write(json.dumps(self.encoder				,	indent=2				,	sort_keys=SCREAMING_SNAKE_CASE__				,	ensure_ascii=SCREAMING_SNAKE_CASE__							) + """\n"""							)

  with open(SCREAMING_SNAKE_CASE__				,	"""w"""				,	encoding="""utf-8"""							) as f:
   __lowerCAmelCase    							=						{v: k for k, v in self.decoder.items()}
   f.write(json.dumps(SCREAMING_SNAKE_CASE__				,	indent=2				,	sort_keys=SCREAMING_SNAKE_CASE__				,	ensure_ascii=SCREAMING_SNAKE_CASE__							) + """\n"""							)

  __lowerCAmelCase    							=						0
  with open(SCREAMING_SNAKE_CASE__				,	"""w"""				,	encoding="""utf-8"""							) as writer:
   for bpe_tokens, token_index in sorted(self.bpe_ranks.items()				,	key=lambda SCREAMING_SNAKE_CASE__							: kv[1]							):
    if index != token_index:
     logger.warning(
         f"""Saving vocabulary to {merges_file}: BPE merge indices are not consecutive."""
         """ Please check that the tokenizer is not corrupted!"""							)
     __lowerCAmelCase    							=						token_index
    writer.write(""" """.join(SCREAMING_SNAKE_CASE__							) + """\n"""							)
    index += 1

  return src_vocab_file, tgt_vocab_file, merges_file
 def __getstate__(				self       :     Union[str, Any]							)  ->   Optional[Any]:
  __lowerCAmelCase    							=						self.__dict__.copy()
  __lowerCAmelCase    							=						None
  return state





 def __setstate__(				self       :     Any				,	SCREAMING_SNAKE_CASE__       :     List[str]							)  ->   Union[str, Any]:
  __lowerCAmelCase    							=						d

  try:
   import sacremoses
  except ImportError:
   raise ImportError(
       """You need to install sacremoses to use XLMTokenizer. """
       """See https://pypi.org/project/sacremoses/ for installation."""							)

  __lowerCAmelCase    							=						sacremoses







'''simple docstring'''

import functools
from math import sqrt
from time import time







def 					UpperCamelCase_						( snake_case_	:	Dict						,		*snake_case_	:	Union[str, Any]						,		**snake_case_	:	List[str]				) ->					List[str]:






 '''simple docstring'''

 __lowerCAmelCase    							=						time()
 __lowerCAmelCase    							=						func(*snake_case_						,		**snake_case_				)
 __lowerCAmelCase    							=						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 					UpperCamelCase_						( snake_case_	:	int				) ->					list[int]:






 '''simple docstring'''

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







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






 '''simple docstring'''

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







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






 '''simple docstring'''

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







def 					UpperCamelCase_						( snake_case_	:	int				) ->					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.
 __lowerCAmelCase    							=						{0: 0, 1: 1, 2: 1}  # Prefilled cache

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

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

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







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






 '''simple docstring'''

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


if __name__ == "__main__":
 _A      :				Optional[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)






