



'''simple docstring'''




import functools
from math import sqrt
from time import time


def     lowerCAmelCase_       (     _lowerCamelCase:       str	,				*_lowerCamelCase:       int	,				**_lowerCamelCase:       Dict ):
		__SCREAMING_SNAKE_CASE	:		Optional[Any]   	=		time()
		__SCREAMING_SNAKE_CASE	:		Union[str, Any]   	=		func(*_lowerCamelCase	,				**_lowerCamelCase )
		__SCREAMING_SNAKE_CASE	:		Optional[int]   	=		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     lowerCAmelCase_       (     _lowerCamelCase:       int ):
		if n < 0:
				raise Exception("""n is negative""" )
		if n == 0:
				return [0]
		__SCREAMING_SNAKE_CASE	:		List[str]   	=		[0, 1]
		for _ in range(n - 1 ):
				fib.append(fib[-1] + fib[-2] )
		return fib


def     lowerCAmelCase_       (     _lowerCamelCase:       int ):

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


def     lowerCAmelCase_       (     _lowerCamelCase:       int ):

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


def     lowerCAmelCase_       (     _lowerCamelCase:       int ):
		if n < 0:
				raise Exception("""n is negative""" )
		# Cache must be outside recursuive function
		# other it will reset every time it calls itself.
		__SCREAMING_SNAKE_CASE	:		dict[int, int]   	=		{0: 0, 1: 1, 2: 1}  # Prefilled cache

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

				__SCREAMING_SNAKE_CASE	:		str   	=		rec_fn_memoized(num - 1 ) + rec_fn_memoized(num - 2 )
				__SCREAMING_SNAKE_CASE	:		Dict   	=		value
				return value

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


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


if __name__ == "__main__":
						UpperCamelCase__	:     List[str]		  =			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'''




UpperCamelCase__	:     List[Any]    =			10_00


def     lowerCAmelCase_       (     _lowerCamelCase:       float ):
		return x * x


def     lowerCAmelCase_       (     _lowerCamelCase:       Any	,				_lowerCamelCase:       float	,				_lowerCamelCase:       float	,				_lowerCamelCase:       int = 4 ):
		assert callable(
		    _lowerCamelCase ), F"the function(object) passed should be callable your input : {function}"
		assert isinstance(_lowerCamelCase	,				(float, int) ), F"a should be float or integer your input : {a}"
		assert isinstance(function(_lowerCamelCase )	,				(float, int) ), (
		    "the function should return integer or float return type of your function, "
		    F"{type(_lowerCamelCase )}"
		)
		assert isinstance(_lowerCamelCase	,				(float, int) ), F"b should be float or integer your input : {b}"
		assert (
		    isinstance(_lowerCamelCase	,				_lowerCamelCase ) and precision > 0
		), F"precision should be positive integer your input : {precision}"

		# just applying the formula of simpson for approximate integration written in
		# mentioned article in first comment of this file and above this function

		__SCREAMING_SNAKE_CASE	:		List[Any]   	=		(b - a) / N_STEPS
		__SCREAMING_SNAKE_CASE	:		List[Any]   	=		function(_lowerCamelCase ) + function(_lowerCamelCase )

		for i in range(1	,				_lowerCamelCase ):
				__SCREAMING_SNAKE_CASE	:		Union[str, Any]   	=		a + h * i
				result += function(_lowerCamelCase ) * (4 if i % 2 else 2)

		result *= h / 3
		return round(_lowerCamelCase	,				_lowerCamelCase )


if __name__ == "__main__":
						import doctest

						doctest.testmod()