



import functools
from math import sqrt
from time import time




def       UpperCAmelCase__	(							__snake_case  ,			*__snake_case  ,			**__snake_case							)				->	Tuple:
  _A          =      time()
  _A          =      func(*__snake_case  ,			**__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) * 1_000:0.4f} ms'''							)
  return output




def       UpperCAmelCase__	(							__snake_case							)				->	list[int]:
  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       UpperCAmelCase__	(							__snake_case							)				->	list[int]:

  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       UpperCAmelCase__	(							__snake_case							)				->	list[int]:

  @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       UpperCAmelCase__	(							__snake_case							)				->	list[int]:
  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(__snake_case							) -> 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(__snake_case							) for i in range(n + 1							)]




def       UpperCAmelCase__	(							__snake_case							)				->	list[int]:
  if n < 0:
    raise Exception('''n is negative'''							)
  if n >= 1_475:
    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								=   3_0
    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)




import math
from timeit import timeit




def       UpperCAmelCase__	(							__snake_case							)				->	int:
  _A          =      0
  _A          =      abs(__snake_case							)
  while True:
    _A          =      n // 10
    digits += 1
    if n == 0:
      break
  return digits




def       UpperCAmelCase__	(							__snake_case							)				->	int:
  return 1 if n == 0 else math.floor(math.log(abs(__snake_case							)  ,			10							) + 1							)




def       UpperCAmelCase__	(							__snake_case							)				->	int:
  return len(str(abs(__snake_case							)							)							)




def       UpperCAmelCase__	(							)				->	None:
  from collections.abc import Callable

  def benchmark_a_function(__snake_case  ,			__snake_case							) -> None:
    _A          =      F'''{func.__name__}({value})'''
    _A          =      timeit(F'''__main__.{call}'''  ,			setup='''import __main__'''							)
    print(F'''{call}: {func(__snake_case							)} -- {timing} seconds'''							)

  for value in (262_144, 1_125_899_906_842_624, 1_267_650_600_228_229_401_496_703_205_376):
    for func in (num_digits, num_digits_fast, num_digits_faster):
      benchmark_a_function(__snake_case  ,			__snake_case							)
    print()


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    benchmark()