



"""simple docstring"""






import functools
import math

import flax.linen as nn
import jax
import jax.numpy as jnp






def 	snake_case__  (						__lowerCamelCase							:       Union[str, Any]				,						__lowerCamelCase							:       List[str]				,						__lowerCamelCase							:       Optional[int]				,						__lowerCamelCase							:       Union[str, Any]				,						__lowerCamelCase							:       int = 4096      ):
			"""simple docstring"""
			lowerCamelCase__      ,  lowerCamelCase__      ,  lowerCamelCase__						:						List[Any]						      =key.shape[-3:]
			lowerCamelCase__						:						Optional[Any]						      =value.shape[-1]
			lowerCamelCase__						:						Any						      =min(__lowerCamelCase				,						__lowerCamelCase      )
			lowerCamelCase__						:						Dict						      =query / jnp.sqrt(__lowerCamelCase      )

			@functools.partial(jax.checkpoint				,						prevent_cse=__lowerCamelCase      )
			def summarize_chunk(__lowerCamelCase							:       Dict				,						__lowerCamelCase							:       List[Any]				,						__lowerCamelCase							:       int      ):
						lowerCamelCase__						:						int						      =jnp.einsum('''...qhd,...khd->...qhk'''				,						__lowerCamelCase				,						__lowerCamelCase				,						precision=__lowerCamelCase      )

						lowerCamelCase__						:						Tuple						      =jnp.max(__lowerCamelCase				,						axis=-1				,						keepdims=__lowerCamelCase      )
						lowerCamelCase__						:						Any						      =jax.lax.stop_gradient(__lowerCamelCase      )
						lowerCamelCase__						:						List[Any]						      =jnp.exp(attn_weights - max_score      )

						lowerCamelCase__						:						List[Any]						      =jnp.einsum('''...vhf,...qhv->...qhf'''				,						__lowerCamelCase				,						__lowerCamelCase				,						precision=__lowerCamelCase      )
						lowerCamelCase__						:						Union[str, Any]						      =jnp.einsum('''...qhk->...qh'''				,						__lowerCamelCase      )

						return (exp_values, exp_weights.sum(axis=-1      ), max_score)

			def chunk_scanner(__lowerCamelCase							:       Union[str, Any]      ):
						# julienne key array
						lowerCamelCase__						:						int						      =jax.lax.dynamic_slice(
						    operand=__lowerCamelCase				,						start_indices=[0] * (key.ndim - 3) + [chunk_idx, 0, 0]				,						slice_sizes=list(key.shape[:-3]      ) + [key_chunk_size, num_heads, k_features]				,						)

						# julienne value array
						lowerCamelCase__						:						Union[str, Any]						      =jax.lax.dynamic_slice(
						    operand=__lowerCamelCase				,						start_indices=[0] * (value.ndim - 3) + [chunk_idx, 0, 0]				,						slice_sizes=list(value.shape[:-3]      ) + [key_chunk_size, num_heads, v_features]				,						)

						return summarize_chunk(__lowerCamelCase				,						__lowerCamelCase				,						__lowerCamelCase      )

			lowerCamelCase__      ,  lowerCamelCase__      ,  lowerCamelCase__						:						int						      =jax.lax.map(f=__lowerCamelCase				,						xs=jnp.arange(0				,						__lowerCamelCase				,						__lowerCamelCase      )      )

			lowerCamelCase__						:						List[str]						      =jnp.max(__lowerCamelCase				,						axis=0				,						keepdims=__lowerCamelCase      )
			lowerCamelCase__						:						Dict						      =jnp.exp(chunk_max - global_max      )

			chunk_values *= jnp.expand_dims(__lowerCamelCase				,						axis=-1      )
			chunk_weights *= max_diffs

			lowerCamelCase__						:						int						      =chunk_values.sum(axis=0      )
			lowerCamelCase__						:						Optional[int]						      =jnp.expand_dims(__lowerCamelCase				,						-1      ).sum(axis=0      )

			return all_values / all_weights






def 	snake_case__  (						__lowerCamelCase							:       Tuple				,						__lowerCamelCase							:       int				,						__lowerCamelCase							:       Optional[int]				,						__lowerCamelCase							:       Optional[int]=jax.lax.Precision.HIGHEST				,						__lowerCamelCase							:       int = 1024				,						__lowerCamelCase							:       int = 4096      ):
			"""simple docstring"""
			lowerCamelCase__      ,  lowerCamelCase__      ,  lowerCamelCase__						:						Dict						      =query.shape[-3:]

			def chunk_scanner(__lowerCamelCase							:       str				,						__lowerCamelCase							:       List[str]      ):
						# julienne query array
						lowerCamelCase__						:						List[str]						      =jax.lax.dynamic_slice(
						    operand=__lowerCamelCase				,						start_indices=([0] * (query.ndim - 3)) + [chunk_idx, 0, 0]				,						slice_sizes=list(query.shape[:-3]      ) + [min(__lowerCamelCase				,						__lowerCamelCase      ), num_heads, q_features]				,						)

						return (
						    chunk_idx + query_chunk_size,  # unused ignore it
						    _query_chunk_attention(
						        query=__lowerCamelCase				,						key=__lowerCamelCase				,						value=__lowerCamelCase				,						precision=__lowerCamelCase				,						key_chunk_size=__lowerCamelCase      ),
						)

			lowerCamelCase__      ,  lowerCamelCase__						:						Optional[Any]						      =jax.lax.scan(
			    f=__lowerCamelCase				,						init=0				,						xs=__lowerCamelCase				,						length=math.ceil(num_q / query_chunk_size      )      )

			return jnp.concatenate(__lowerCamelCase				,						axis=-3      )  # fuse the chunked result back

class 			__SCREAMING_SNAKE_CASE      ( nn.Module  ):


					'''simple docstring'''





					_a       =				42
					_a       =				8
					_a       =				6_4
					_a       =				0.0
					_a       =				False
					_a       =				jnp.floataa



					def 						snake_case			(			self				:    Dict	)->   str:
								lowerCamelCase__						:						str						      =self.dim_head * self.heads
								lowerCamelCase__						:						List[Any]						      =self.dim_head**-0.5

								# Weights were exported with old names {to_q, to_k, to_v, to_out}
								lowerCamelCase__						:						Tuple						      =nn.Dense(lowerCamelCase,    use_bias=lowerCamelCase,    dtype=self.dtype,    name='''to_q'''	)
								lowerCamelCase__						:						Optional[int]						      =nn.Dense(lowerCamelCase,    use_bias=lowerCamelCase,    dtype=self.dtype,    name='''to_k'''	)
								lowerCamelCase__						:						List[Any]						      =nn.Dense(lowerCamelCase,    use_bias=lowerCamelCase,    dtype=self.dtype,    name='''to_v'''	)

								lowerCamelCase__						:						Any						      =nn.Dense(self.query_dim,    dtype=self.dtype,    name='''to_out_0'''	)
								lowerCamelCase__						:						List[Any]						      =nn.Dropout(rate=self.dropout	)



					def 						snake_case			(			self				:    Any,    lowerCamelCase				:    str	)->   Any:
								lowerCamelCase__      ,  lowerCamelCase__      ,  lowerCamelCase__						:						Union[str, Any]						      =tensor.shape
								lowerCamelCase__						:						List[Any]						      =self.heads
								lowerCamelCase__						:						str						      =tensor.reshape(lowerCamelCase,    lowerCamelCase,    lowerCamelCase,    dim // head_size	)
								lowerCamelCase__						:						Union[str, Any]						      =jnp.transpose(lowerCamelCase,    (0, 2, 1, 3)	)
								lowerCamelCase__						:						Union[str, Any]						      =tensor.reshape(batch_size * head_size,    lowerCamelCase,    dim // head_size	)
								return tensor



					def 						snake_case			(			self				:    Tuple,    lowerCamelCase				:    int	)->   Union[str, Any]:
								lowerCamelCase__      ,  lowerCamelCase__      ,  lowerCamelCase__						:						List[Any]						      =tensor.shape
								lowerCamelCase__						:						str						      =self.heads
								lowerCamelCase__						:						Dict						      =tensor.reshape(batch_size // head_size,    lowerCamelCase,    lowerCamelCase,    lowerCamelCase	)
								lowerCamelCase__						:						Optional[Any]						      =jnp.transpose(lowerCamelCase,    (0, 2, 1, 3)	)
								lowerCamelCase__						:						Optional[Any]						      =tensor.reshape(batch_size // head_size,    lowerCamelCase,    dim * head_size	)
								return tensor




					def __call__(			self				:    Optional[int],    lowerCamelCase				:    Union[str, Any],    lowerCamelCase				:    Tuple=None,    lowerCamelCase				:    Tuple=True	)->   Union[str, Any]:
								lowerCamelCase__						:						Optional[Any]						      =hidden_states if context is None else context

								lowerCamelCase__						:						Any						      =self.query(lowerCamelCase	)
								lowerCamelCase__						:						Any						      =self.key(lowerCamelCase	)
								lowerCamelCase__						:						Tuple						      =self.value(lowerCamelCase	)

								lowerCamelCase__						:						int						      =self.reshape_heads_to_batch_dim(lowerCamelCase	)
								lowerCamelCase__						:						Union[str, Any]						      =self.reshape_heads_to_batch_dim(lowerCamelCase	)
								lowerCamelCase__						:						int						      =self.reshape_heads_to_batch_dim(lowerCamelCase	)

								if self.use_memory_efficient_attention:
											lowerCamelCase__						:						Tuple						      =query_states.transpose(1,    0,    2	)
											lowerCamelCase__						:						Any						      =key_states.transpose(1,    0,    2	)
											lowerCamelCase__						:						Any						      =value_states.transpose(1,    0,    2	)

											# this if statement create a chunk size for each layer of the unet
											# the chunk size is equal to the query_length dimension of the deepest layer of the unet

											lowerCamelCase__						:						Optional[Any]						      =query_states.shape[-3]
											if flatten_latent_dim % 64 == 0:
														lowerCamelCase__						:						Union[str, Any]						      =int(flatten_latent_dim / 64	)
											elif flatten_latent_dim % 16 == 0:
														lowerCamelCase__						:						Tuple						      =int(flatten_latent_dim / 16	)
											elif flatten_latent_dim % 4 == 0:
														lowerCamelCase__						:						Dict						      =int(flatten_latent_dim / 4	)
											else:
														lowerCamelCase__						:						Tuple						      =int(lowerCamelCase	)

											lowerCamelCase__						:						Optional[Any]						      =jax_memory_efficient_attention(
											    lowerCamelCase,    lowerCamelCase,    lowerCamelCase,    query_chunk_size=lowerCamelCase,    key_chunk_size=4096 * 4	)

											lowerCamelCase__						:						Dict						      =hidden_states.transpose(1,    0,    2	)
								else:
											# compute attentions
											lowerCamelCase__						:						Dict						      =jnp.einsum('''b i d, b j d->b i j''',    lowerCamelCase,    lowerCamelCase	)
											lowerCamelCase__						:						Dict						      =attention_scores * self.scale
											lowerCamelCase__						:						Optional[int]						      =nn.softmax(lowerCamelCase,    axis=2	)

											# attend to values
											lowerCamelCase__						:						int						      =jnp.einsum('''b i j, b j d -> b i d''',    lowerCamelCase,    lowerCamelCase	)

								lowerCamelCase__						:						Union[str, Any]						      =self.reshape_batch_dim_to_heads(lowerCamelCase	)
								lowerCamelCase__						:						Tuple						      =self.proj_attn(lowerCamelCase	)
								return self.dropout_layer(lowerCamelCase,    deterministic=lowerCamelCase	)





class 			__SCREAMING_SNAKE_CASE      ( nn.Module  ):


					'''simple docstring'''





					_a       =				42
					_a       =				42
					_a       =				42
					_a       =				0.0
					_a       =				False
					_a       =				jnp.floataa
					_a       =				False



					def 						snake_case			(			self				:    Union[str, Any]	)->   int:
								# self attention (or cross_attention if only_cross_attention is True)
								lowerCamelCase__						:						Union[str, Any]						      =FlaxAttention(
								    self.dim,    self.n_heads,    self.d_head,    self.dropout,    self.use_memory_efficient_attention,    dtype=self.dtype	)
								# cross attention
								lowerCamelCase__						:						Union[str, Any]						      =FlaxAttention(
								    self.dim,    self.n_heads,    self.d_head,    self.dropout,    self.use_memory_efficient_attention,    dtype=self.dtype	)
								lowerCamelCase__						:						Optional[Any]						      =FlaxFeedForward(dim=self.dim,    dropout=self.dropout,    dtype=self.dtype	)
								lowerCamelCase__						:						Tuple						      =nn.LayerNorm(epsilon=1E-5,    dtype=self.dtype	)
								lowerCamelCase__						:						Optional[Any]						      =nn.LayerNorm(epsilon=1E-5,    dtype=self.dtype	)
								lowerCamelCase__						:						Optional[int]						      =nn.LayerNorm(epsilon=1E-5,    dtype=self.dtype	)
								lowerCamelCase__						:						Union[str, Any]						      =nn.Dropout(rate=self.dropout	)




					def __call__(			self				:    str,    lowerCamelCase				:    int,    lowerCamelCase				:    Tuple,    lowerCamelCase				:    Optional[int]=True	)->   Any:
								# self attention
								lowerCamelCase__						:						Optional[Any]						      =hidden_states
								if self.only_cross_attention:
											lowerCamelCase__						:						List[str]						      =self.attna(self.norma(lowerCamelCase	),    lowerCamelCase,    deterministic=lowerCamelCase	)
								else:
											lowerCamelCase__						:						str						      =self.attna(self.norma(lowerCamelCase	),    deterministic=lowerCamelCase	)
								lowerCamelCase__						:						Tuple						      =hidden_states + residual

								# cross attention
								lowerCamelCase__						:						Any						      =hidden_states
								lowerCamelCase__						:						Dict						      =self.attna(self.norma(lowerCamelCase	),    lowerCamelCase,    deterministic=lowerCamelCase	)
								lowerCamelCase__						:						Dict						      =hidden_states + residual

								# feed forward
								lowerCamelCase__						:						Optional[int]						      =hidden_states
								lowerCamelCase__						:						str						      =self.ff(self.norma(lowerCamelCase	),    deterministic=lowerCamelCase	)
								lowerCamelCase__						:						Union[str, Any]						      =hidden_states + residual

								return self.dropout_layer(lowerCamelCase,    deterministic=lowerCamelCase	)





class 			__SCREAMING_SNAKE_CASE      ( nn.Module  ):


					'''simple docstring'''





					_a       =				42
					_a       =				42
					_a       =				42
					_a       =				1
					_a       =				0.0
					_a       =				False
					_a       =				False
					_a       =				jnp.floataa
					_a       =				False



					def 						snake_case			(			self				:    str	)->   Optional[int]:
								lowerCamelCase__						:						Optional[int]						      =nn.GroupNorm(num_groups=32,    epsilon=1E-5	)

								lowerCamelCase__						:						Optional[Any]						      =self.n_heads * self.d_head
								if self.use_linear_projection:
											lowerCamelCase__						:						int						      =nn.Dense(lowerCamelCase,    dtype=self.dtype	)
								else:
											lowerCamelCase__						:						Union[str, Any]						      =nn.Conv(
											    lowerCamelCase,    kernel_size=(1, 1),    strides=(1, 1),    padding='''VALID''',    dtype=self.dtype,    )

								lowerCamelCase__						:						Optional[Any]						      =[
								    FlaxBasicTransformerBlock(
								        lowerCamelCase,    self.n_heads,    self.d_head,    dropout=self.dropout,    only_cross_attention=self.only_cross_attention,    dtype=self.dtype,    use_memory_efficient_attention=self.use_memory_efficient_attention,    )
								    for _ in range(self.depth	)
								]

								if self.use_linear_projection:
											lowerCamelCase__						:						Optional[int]						      =nn.Dense(lowerCamelCase,    dtype=self.dtype	)
								else:
											lowerCamelCase__						:						Union[str, Any]						      =nn.Conv(
											    lowerCamelCase,    kernel_size=(1, 1),    strides=(1, 1),    padding='''VALID''',    dtype=self.dtype,    )

								lowerCamelCase__						:						int						      =nn.Dropout(rate=self.dropout	)




					def __call__(			self				:    Any,    lowerCamelCase				:    Tuple,    lowerCamelCase				:    str,    lowerCamelCase				:    str=True	)->   Any:
								lowerCamelCase__      ,  lowerCamelCase__      ,  lowerCamelCase__      ,  lowerCamelCase__						:						str						      =hidden_states.shape
								lowerCamelCase__						:						List[str]						      =hidden_states
								lowerCamelCase__						:						int						      =self.norm(lowerCamelCase	)
								if self.use_linear_projection:
											lowerCamelCase__						:						Union[str, Any]						      =hidden_states.reshape(lowerCamelCase,    height * width,    lowerCamelCase	)
											lowerCamelCase__						:						Dict						      =self.proj_in(lowerCamelCase	)
								else:
											lowerCamelCase__						:						Union[str, Any]						      =self.proj_in(lowerCamelCase	)
											lowerCamelCase__						:						Any						      =hidden_states.reshape(lowerCamelCase,    height * width,    lowerCamelCase	)

								for transformer_block in self.transformer_blocks:
											lowerCamelCase__						:						Optional[Any]						      =transformer_block(lowerCamelCase,    lowerCamelCase,    deterministic=lowerCamelCase	)

								if self.use_linear_projection:
											lowerCamelCase__						:						Dict						      =self.proj_out(lowerCamelCase	)
											lowerCamelCase__						:						Optional[int]						      =hidden_states.reshape(lowerCamelCase,    lowerCamelCase,    lowerCamelCase,    lowerCamelCase	)
								else:
											lowerCamelCase__						:						Optional[Any]						      =hidden_states.reshape(lowerCamelCase,    lowerCamelCase,    lowerCamelCase,    lowerCamelCase	)
											lowerCamelCase__						:						str						      =self.proj_out(lowerCamelCase	)

								lowerCamelCase__						:						List[Any]						      =hidden_states + residual
								return self.dropout_layer(lowerCamelCase,    deterministic=lowerCamelCase	)





class 			__SCREAMING_SNAKE_CASE      ( nn.Module  ):


					'''simple docstring'''





					_a       =				42
					_a       =				0.0
					_a       =				jnp.floataa



					def 						snake_case			(			self				:    Tuple	)->   Optional[Any]:
								# The second linear layer needs to be called
								# net_2 for now to match the index of the Sequential layer
								lowerCamelCase__						:						List[str]						      =FlaxGEGLU(self.dim,    self.dropout,    self.dtype	)
								lowerCamelCase__						:						Union[str, Any]						      =nn.Dense(self.dim,    dtype=self.dtype	)




					def __call__(			self				:    List[Any],    lowerCamelCase				:    Union[str, Any],    lowerCamelCase				:    Optional[int]=True	)->   Optional[int]:
								lowerCamelCase__						:						Dict						      =self.net_a(lowerCamelCase,    deterministic=lowerCamelCase	)
								lowerCamelCase__						:						str						      =self.net_a(lowerCamelCase	)
								return hidden_states





class 			__SCREAMING_SNAKE_CASE      ( nn.Module  ):


					'''simple docstring'''





					_a       =				42
					_a       =				0.0
					_a       =				jnp.floataa



					def 						snake_case			(			self				:    Optional[int]	)->   Dict:
								lowerCamelCase__						:						str						      =self.dim * 4
								lowerCamelCase__						:						Union[str, Any]						      =nn.Dense(inner_dim * 2,    dtype=self.dtype	)
								lowerCamelCase__						:						Dict						      =nn.Dropout(rate=self.dropout	)




					def __call__(			self				:    Optional[int],    lowerCamelCase				:    Any,    lowerCamelCase				:    Dict=True	)->   str:
								lowerCamelCase__						:						int						      =self.proj(lowerCamelCase	)
								lowerCamelCase__      ,  lowerCamelCase__						:						Union[str, Any]						      =jnp.split(lowerCamelCase,    2,    axis=2	)
								return self.dropout_layer(hidden_linear * nn.gelu(lowerCamelCase	),    deterministic=lowerCamelCase	)






import functools
from math import sqrt
from time import time

def    UpperCamelCase_ (	a_  ,				*a_  ,				**a_		)     ->List[Any]:
		A				=time()
		A				=func(*a_  ,				**a_		)
		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) * 1000:0.4f} ms'''		)
		return output

def    UpperCamelCase_ (	a_		)     ->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_ (	a_		)     ->list[int]:

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

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

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

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

def    UpperCamelCase_ (	a_		)     ->list[int]:
		if n < 0:
				raise Exception("n is negative"		)
		if n >= 1475:
				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__":
	__a							  =						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)




