
import mpmath  # for roots of unity
import numpy as np



class 			lowerCAmelCase_		:


				"""simple docstring"""



				def __init__(self     , SCREAMING_SNAKE_CASE__=None     , SCREAMING_SNAKE_CASE__=None					)      ->	Any:



											"""simple docstring"""




											SCREAMING_SNAKE_CASE__		: Optional[int]     =     list(poly_a or [0]					)[:]
											SCREAMING_SNAKE_CASE__		: Optional[Any]     =     list(poly_b or [0]					)[:]

											# Remove leading zero coefficients
											while self.polyA[-1] == 0:
																		self.polyA.pop()
											SCREAMING_SNAKE_CASE__		: Any     =     len(self.polyA					)

											while self.polyB[-1] == 0:
																		self.polyB.pop()
											SCREAMING_SNAKE_CASE__		: Dict     =     len(self.polyB					)

											# Add 0 to make lengths equal a power of 2
											SCREAMING_SNAKE_CASE__		: int     =     int(
											    2 ** np.ceil(np.loga(len(self.polyA					) + len(self.polyB					) - 1					)					)					)

											while len(self.polyA					) < self.c_max_length:
																		self.polyA.append(0					)
											while len(self.polyB					) < self.c_max_length:
																		self.polyB.append(0					)
											# A complex root used for the fourier transform
											SCREAMING_SNAKE_CASE__		: Union[str, Any]     =     complex(mpmath.root(x=1     , n=self.c_max_length     , k=1					)					)

											# The product
											SCREAMING_SNAKE_CASE__		: Tuple     =     self.__multiply()



				def 			__magic_name__					(self     , SCREAMING_SNAKE_CASE__					)      ->	List[str]:



											"""simple docstring"""




											SCREAMING_SNAKE_CASE__		: Union[str, Any]     =     [[x] for x in self.polyA] if which == '''A''' else [[x] for x in self.polyB]
											# Corner case
											if len(UpperCAmelCase__					) <= 1:
																		return dft[0]
											#
											SCREAMING_SNAKE_CASE__		: Any     =     self.c_max_length // 2
											while next_ncol > 0:
																		SCREAMING_SNAKE_CASE__		: Optional[int]     =     [[] for i in range(UpperCAmelCase__					)]
																		SCREAMING_SNAKE_CASE__		: Tuple     =     self.root**next_ncol

																		# First half of next step
																		SCREAMING_SNAKE_CASE__		: str     =     1
																		for j in range(self.c_max_length // (next_ncol * 2)					):
																									for i in range(UpperCAmelCase__					):
																																new_dft[i].append(dft[i][j] + current_root * dft[i + next_ncol][j]					)
																									current_root *= root
																		# Second half of next step
																		SCREAMING_SNAKE_CASE__		: int     =     1
																		for j in range(self.c_max_length // (next_ncol * 2)					):
																									for i in range(UpperCAmelCase__					):
																																new_dft[i].append(dft[i][j] - current_root * dft[i + next_ncol][j]					)
																									current_root *= root
																		# Update
																		SCREAMING_SNAKE_CASE__		: Dict     =     new_dft
																		SCREAMING_SNAKE_CASE__		: Tuple     =     next_ncol // 2
											return dft[0]



				def 			__magic_name__					(self					)      ->	Dict:



											"""simple docstring"""




											SCREAMING_SNAKE_CASE__		: Any     =     self.__dft("""A"""					)
											SCREAMING_SNAKE_CASE__		: Any     =     self.__dft("""B"""					)
											SCREAMING_SNAKE_CASE__		: Optional[int]     =     [[dft_a[i] * dft_b[i] for i in range(self.c_max_length					)]]
											del dft_a
											del dft_b

											# Corner Case
											if len(inverce_c[0]					) <= 1:
																		return inverce_c[0]
											# Inverse DFT
											SCREAMING_SNAKE_CASE__		: Optional[int]     =     2
											while next_ncol <= self.c_max_length:
																		SCREAMING_SNAKE_CASE__		: Optional[int]     =     [[] for i in range(UpperCAmelCase__					)]
																		SCREAMING_SNAKE_CASE__		: List[str]     =     self.root ** (next_ncol // 2)
																		SCREAMING_SNAKE_CASE__		: Optional[int]     =     1
																		# First half of next step
																		for j in range(self.c_max_length // next_ncol					):
																									for i in range(next_ncol // 2					):
																																# Even positions
																																new_inverse_c[i].append(
																																    (
																																        inverce_c[i][j]
																																        + inverce_c[i][j + self.c_max_length // next_ncol]
																																    )
																																    / 2					)
																																# Odd positions
																																new_inverse_c[i + next_ncol // 2].append(
																																    (
																																        inverce_c[i][j]
																																        - inverce_c[i][j + self.c_max_length // next_ncol]
																																    )
																																    / (2 * current_root)					)
																									current_root *= root
																		# Update
																		SCREAMING_SNAKE_CASE__		: List[Any]     =     new_inverse_c
																		next_ncol *= 2
											# Unpack
											SCREAMING_SNAKE_CASE__		: Tuple     =     [round(x[0].real     , 8					) + round(x[0].imag     , 8					) * 1j for x in inverce_c]

											# Remove leading 0's
											while inverce_c[-1] == 0:
																		inverce_c.pop()
											return inverce_c



				def __str__(self					)      ->	str:



											"""simple docstring"""




											SCREAMING_SNAKE_CASE__		: Any     =     '''A = ''' + ''' + '''.join(
											    F'''{coef}*x^{i}''' for coef, i in enumerate(self.polyA[: self.len_A]					)					)
											SCREAMING_SNAKE_CASE__		: Tuple     =     '''B = ''' + ''' + '''.join(
											    F'''{coef}*x^{i}''' for coef, i in enumerate(self.polyB[: self.len_B]					)					)
											SCREAMING_SNAKE_CASE__		: List[str]     =     '''A*B = ''' + ''' + '''.join(
											    F'''{coef}*x^{i}''' for coef, i in enumerate(self.product					)					)

											return F'''{a}\n{b}\n{c}'''


# Unit tests
if __name__ == "__main__":
					import doctest

					doctest.testmod()






"""simple docstring"""




from manim import *



class 			lowerCAmelCase_		(a__						):


				"""simple docstring"""



				def 			__magic_name__					(self					)      ->	Any:



											"""simple docstring"""




											SCREAMING_SNAKE_CASE__		: Dict     =     Rectangle(height=0.5     , width=0.5					)
											SCREAMING_SNAKE_CASE__		: Dict     =     Rectangle(height=0.46     , width=0.46					).set_stroke(width=0					)

											SCREAMING_SNAKE_CASE__		: Optional[Any]     =     Rectangle(height=0.25     , width=0.25					)

											SCREAMING_SNAKE_CASE__		: Any     =     [mem.copy() for i in range(6					)]
											SCREAMING_SNAKE_CASE__		: int     =     [mem.copy() for i in range(6					)]
											SCREAMING_SNAKE_CASE__		: Any     =     VGroup(*SCREAMING_SNAKE_CASE__					).arrange(SCREAMING_SNAKE_CASE__     , buff=0					)
											SCREAMING_SNAKE_CASE__		: Any     =     VGroup(*SCREAMING_SNAKE_CASE__					).arrange(SCREAMING_SNAKE_CASE__     , buff=0					)
											SCREAMING_SNAKE_CASE__		: Optional[int]     =     VGroup(SCREAMING_SNAKE_CASE__     , SCREAMING_SNAKE_CASE__					).arrange(SCREAMING_SNAKE_CASE__     , buff=0					)
											SCREAMING_SNAKE_CASE__		: List[str]     =     Text("""CPU"""     , font_size=24					)
											SCREAMING_SNAKE_CASE__		: Union[str, Any]     =     Group(SCREAMING_SNAKE_CASE__     , SCREAMING_SNAKE_CASE__					).arrange(SCREAMING_SNAKE_CASE__     , buff=0.5     , aligned_edge=SCREAMING_SNAKE_CASE__					)
											cpu.move_to([-2.5, -0.5, 0]					)
											self.add(SCREAMING_SNAKE_CASE__					)

											SCREAMING_SNAKE_CASE__		: List[Any]     =     [mem.copy() for i in range(4					)]
											SCREAMING_SNAKE_CASE__		: List[Any]     =     VGroup(*SCREAMING_SNAKE_CASE__					).arrange(SCREAMING_SNAKE_CASE__     , buff=0					)
											SCREAMING_SNAKE_CASE__		: Any     =     Text("""GPU"""     , font_size=24					)
											SCREAMING_SNAKE_CASE__		: int     =     Group(SCREAMING_SNAKE_CASE__     , SCREAMING_SNAKE_CASE__					).arrange(SCREAMING_SNAKE_CASE__     , buff=0.5     , aligned_edge=SCREAMING_SNAKE_CASE__					)
											gpu.move_to([-1, -1, 0]					)
											self.add(SCREAMING_SNAKE_CASE__					)

											SCREAMING_SNAKE_CASE__		: List[Any]     =     [mem.copy() for i in range(6					)]
											SCREAMING_SNAKE_CASE__		: Optional[Any]     =     VGroup(*SCREAMING_SNAKE_CASE__					).arrange(SCREAMING_SNAKE_CASE__     , buff=0					)

											SCREAMING_SNAKE_CASE__		: Tuple     =     Text("""Model"""     , font_size=24					)
											SCREAMING_SNAKE_CASE__		: Dict     =     Group(SCREAMING_SNAKE_CASE__     , SCREAMING_SNAKE_CASE__					).arrange(SCREAMING_SNAKE_CASE__     , buff=0.5     , aligned_edge=SCREAMING_SNAKE_CASE__					)
											model.move_to([3, -1.0, 0]					)
											self.add(SCREAMING_SNAKE_CASE__					)

											SCREAMING_SNAKE_CASE__		: Optional[Any]     =     []
											SCREAMING_SNAKE_CASE__		: Any     =     []

											for i, rect in enumerate(SCREAMING_SNAKE_CASE__					):
																		SCREAMING_SNAKE_CASE__		: List[str]     =     fill.copy().set_fill(SCREAMING_SNAKE_CASE__     , opacity=0.8					)
																		target.move_to(SCREAMING_SNAKE_CASE__					)
																		model_arr.append(SCREAMING_SNAKE_CASE__					)

																		SCREAMING_SNAKE_CASE__		: List[str]     =     Rectangle(height=0.46     , width=0.46					).set_stroke(width=0.0					).set_fill(SCREAMING_SNAKE_CASE__     , opacity=0.8					)
																		cpu_target.move_to(cpu_left_col_base[i]					)
																		model_cpu_arr.append(SCREAMING_SNAKE_CASE__					)

											self.add(*SCREAMING_SNAKE_CASE__     , *SCREAMING_SNAKE_CASE__					)

											SCREAMING_SNAKE_CASE__		: Tuple     =     [meta_mem.copy() for i in range(6					)]
											SCREAMING_SNAKE_CASE__		: List[str]     =     [meta_mem.copy() for i in range(6					)]
											SCREAMING_SNAKE_CASE__		: Any     =     VGroup(*SCREAMING_SNAKE_CASE__					).arrange(SCREAMING_SNAKE_CASE__     , buff=0					)
											SCREAMING_SNAKE_CASE__		: int     =     VGroup(*SCREAMING_SNAKE_CASE__					).arrange(SCREAMING_SNAKE_CASE__     , buff=0					)
											SCREAMING_SNAKE_CASE__		: Union[str, Any]     =     VGroup(SCREAMING_SNAKE_CASE__     , SCREAMING_SNAKE_CASE__					).arrange(SCREAMING_SNAKE_CASE__     , buff=0					)
											SCREAMING_SNAKE_CASE__		: Union[str, Any]     =     Text("""Disk"""     , font_size=24					)
											SCREAMING_SNAKE_CASE__		: Any     =     Group(SCREAMING_SNAKE_CASE__     , SCREAMING_SNAKE_CASE__					).arrange(SCREAMING_SNAKE_CASE__     , buff=0.5     , aligned_edge=SCREAMING_SNAKE_CASE__					)
											disk.move_to([-4, -1.25, 0]					)
											self.add(SCREAMING_SNAKE_CASE__     , SCREAMING_SNAKE_CASE__					)

											SCREAMING_SNAKE_CASE__		: Any     =     Square(side_length=2.2					)
											key.move_to([-5, 2, 0]					)

											SCREAMING_SNAKE_CASE__		: List[str]     =     MarkupText(
											    F'''<b>Key:</b>\n\n<span fgcolor=\'{YELLOW}\'>●</span> Empty Model'''     , font_size=18     , )

											key_text.move_to([-5, 2.4, 0]					)

											self.add(SCREAMING_SNAKE_CASE__     , SCREAMING_SNAKE_CASE__					)

											SCREAMING_SNAKE_CASE__		: Any     =     MarkupText(
											    F'''<span fgcolor=\'{BLUE}\'>●</span> Checkpoint'''     , font_size=18     , )

											blue_text.next_to(SCREAMING_SNAKE_CASE__     , DOWN * 2.4     , aligned_edge=key_text.get_left()					)
											self.add(SCREAMING_SNAKE_CASE__					)

											SCREAMING_SNAKE_CASE__		: Union[str, Any]     =     MarkupText(
											    F'''Now watch as an input is passed through the model\nand how the memory is utilized and handled.'''     , font_size=24     , )
											step_a.move_to([2, 2, 0]					)

											self.play(Write(SCREAMING_SNAKE_CASE__					)					)

											SCREAMING_SNAKE_CASE__		: Dict     =     Square(0.3					)
											input.set_fill(SCREAMING_SNAKE_CASE__     , opacity=1.0					)
											input.set_stroke(width=0.0					)
											input.next_to(model_base[0]     , SCREAMING_SNAKE_CASE__     , buff=0.5					)

											self.play(Write(SCREAMING_SNAKE_CASE__					)					)

											input.generate_target()
											input.target.next_to(model_arr[0]     , direction=SCREAMING_SNAKE_CASE__     , buff=0.02					)
											self.play(MoveToTarget(SCREAMING_SNAKE_CASE__					)					)

											self.play(FadeOut(SCREAMING_SNAKE_CASE__					)					)

											SCREAMING_SNAKE_CASE__		: Optional[Any]     =     Arrow(start=SCREAMING_SNAKE_CASE__     , end=SCREAMING_SNAKE_CASE__     , color=SCREAMING_SNAKE_CASE__     , buff=0.5					)
											a.next_to(model_arr[0].get_left()     , SCREAMING_SNAKE_CASE__     , buff=0.2					)

											model_cpu_arr[0].generate_target()
											model_cpu_arr[0].target.move_to(gpu_rect[0]					)

											SCREAMING_SNAKE_CASE__		: Tuple     =     MarkupText(
											    F'''As the input reaches a layer, the hook triggers\nand weights are moved from the CPU\nto the GPU and back.'''     , font_size=24     , )
											step_a.move_to([2, 2, 0]					)

											self.play(Write(SCREAMING_SNAKE_CASE__     , run_time=3					)					)

											SCREAMING_SNAKE_CASE__		: Tuple     =     {"""run_time""": 1, """fade_in""": True, """fade_out""": True, """buff""": 0.02}

											self.play(
											    Write(SCREAMING_SNAKE_CASE__					)     , Circumscribe(model_arr[0]     , color=SCREAMING_SNAKE_CASE__     , **SCREAMING_SNAKE_CASE__					)     , Circumscribe(model_cpu_arr[0]     , color=SCREAMING_SNAKE_CASE__     , **SCREAMING_SNAKE_CASE__					)     , Circumscribe(gpu_rect[0]     , color=SCREAMING_SNAKE_CASE__     , **SCREAMING_SNAKE_CASE__					)     , )
											self.play(MoveToTarget(model_cpu_arr[0]					)					)

											SCREAMING_SNAKE_CASE__		: Optional[Any]     =     a.copy()
											for i in range(6					):
																		a_c.next_to(model_arr[i].get_right() + 0.02     , SCREAMING_SNAKE_CASE__     , buff=0.2					)

																		input.generate_target()
																		input.target.move_to(model_arr[i].get_right() + 0.02					)

																		SCREAMING_SNAKE_CASE__		: Optional[Any]     =     AnimationGroup(
																		    FadeOut(SCREAMING_SNAKE_CASE__     , run_time=0.5					)     , MoveToTarget(SCREAMING_SNAKE_CASE__     , run_time=0.5					)     , FadeIn(SCREAMING_SNAKE_CASE__     , run_time=0.5					)     , lag_ratio=0.2					)

																		self.play(SCREAMING_SNAKE_CASE__					)

																		model_cpu_arr[i].generate_target()
																		model_cpu_arr[i].target.move_to(cpu_left_col_base[i]					)

																		if i < 5:
																									model_cpu_arr[i + 1].generate_target()
																									model_cpu_arr[i + 1].target.move_to(gpu_rect[0]					)
																									if i >= 1:
																																SCREAMING_SNAKE_CASE__		: Union[str, Any]     =     0.7

																									self.play(
																									    Circumscribe(model_arr[i]     , **SCREAMING_SNAKE_CASE__					)     , Circumscribe(cpu_left_col_base[i]     , **SCREAMING_SNAKE_CASE__					)     , Circumscribe(cpu_left_col_base[i + 1]     , color=SCREAMING_SNAKE_CASE__     , **SCREAMING_SNAKE_CASE__					)     , Circumscribe(gpu_rect[0]     , color=SCREAMING_SNAKE_CASE__     , **SCREAMING_SNAKE_CASE__					)     , Circumscribe(model_arr[i + 1]     , color=SCREAMING_SNAKE_CASE__     , **SCREAMING_SNAKE_CASE__					)     , )
																									if i < 1:
																																self.play(
																																    MoveToTarget(model_cpu_arr[i]					)     , MoveToTarget(model_cpu_arr[i + 1]					)     , )
																									else:
																																self.play(
																																    MoveToTarget(model_cpu_arr[i]     , run_time=0.7					)     , MoveToTarget(model_cpu_arr[i + 1]     , run_time=0.7					)     , )
																		else:
																									model_cpu_arr[i].generate_target()
																									model_cpu_arr[i].target.move_to(cpu_left_col_base[-1]					)
																									input.generate_target()
																									input.target.next_to(model_arr[-1].get_right()     , RIGHT + 0.02     , buff=0.2					)

																									self.play(
																									    Circumscribe(model_arr[-1]     , color=SCREAMING_SNAKE_CASE__     , **SCREAMING_SNAKE_CASE__					)     , Circumscribe(cpu_left_col_base[-1]     , color=SCREAMING_SNAKE_CASE__     , **SCREAMING_SNAKE_CASE__					)     , Circumscribe(gpu_rect[0]     , color=SCREAMING_SNAKE_CASE__     , **SCREAMING_SNAKE_CASE__					)     , )

																									self.play(MoveToTarget(model_cpu_arr[i]					)					)

																		SCREAMING_SNAKE_CASE__		: Union[str, Any]     =     a_c
																		SCREAMING_SNAKE_CASE__		: Optional[Any]     =     a_c.copy()

											input.generate_target()
											input.target.next_to(model_base[-1]     , RIGHT + 0.02     , buff=0.5					)
											self.play(
											    FadeOut(SCREAMING_SNAKE_CASE__					)     , FadeOut(SCREAMING_SNAKE_CASE__     , run_time=0.5					)     , )

											SCREAMING_SNAKE_CASE__		: Dict     =     MarkupText(F'''Inference on a model too large for GPU memory\nis successfully completed.'''     , font_size=24					)
											step_a.move_to([2, 2, 0]					)

											self.play(Write(SCREAMING_SNAKE_CASE__     , run_time=3					)     , MoveToTarget(SCREAMING_SNAKE_CASE__					)					)

											self.wait()




