





'''simple docstring'''

import mpmath  # for roots of unity
import numpy as np







class __a			:





   def __init__(       self					:      Dict					,lowerCamelCase					:      str=None					,lowerCamelCase					:      str=None     ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE   				=							list(poly_a or [0]     )[:]
      __SCREAMING_SNAKE_CASE   				=							list(poly_b or [0]     )[:]

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

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

      # Add 0 to make lengths equal a power of 2
      __SCREAMING_SNAKE_CASE   				=							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   				=							complex(mpmath.root(x=1					,n=self.c_max_length					,k=1     )     )

      # The product
      __SCREAMING_SNAKE_CASE   				=							self.__multiply()





   def   UpperCAmelCase__  (       self					:      List[str]					,lowerCamelCase					:      int     ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE   				=							[[x] for x in self.polyA] if which == """A""" else [[x] for x in self.polyB]
      # Corner case
      if len(lowerCamelCase     ) <= 1:
         return dft[0]
      #
      __SCREAMING_SNAKE_CASE   				=							self.c_max_length // 2
      while next_ncol > 0:
         __SCREAMING_SNAKE_CASE   				=							[[] for i in range(lowerCamelCase     )]
         __SCREAMING_SNAKE_CASE   				=							self.root**next_ncol

         # First half of next step
         __SCREAMING_SNAKE_CASE   				=							1
         for j in range(self.c_max_length // (next_ncol * 2)     ):
            for i in range(lowerCamelCase     ):
               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   				=							1
         for j in range(self.c_max_length // (next_ncol * 2)     ):
            for i in range(lowerCamelCase     ):
               new_dft[i].append(dft[i][j] - current_root * dft[i + next_ncol][j]     )
            current_root *= root
         # Update
         __SCREAMING_SNAKE_CASE   				=							new_dft
         __SCREAMING_SNAKE_CASE   				=							next_ncol // 2
      return dft[0]





   def   UpperCAmelCase__  (       self					:      str     ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE   				=							self.__dft("""A"""     )
      __SCREAMING_SNAKE_CASE   				=							self.__dft("""B"""     )
      __SCREAMING_SNAKE_CASE   				=							[[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   				=							2
      while next_ncol <= self.c_max_length:
         __SCREAMING_SNAKE_CASE   				=							[[] for i in range(lowerCamelCase     )]
         __SCREAMING_SNAKE_CASE   				=							self.root ** (next_ncol // 2)
         __SCREAMING_SNAKE_CASE   				=							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   				=							new_inverse_c
         next_ncol *= 2
      # Unpack
      __SCREAMING_SNAKE_CASE   				=							[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					:      Optional[Any]     ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE   				=							"""A = """ + """ + """.join(
          f"""{coef}*x^{i}""" for coef, i in enumerate(self.polyA[: self.len_A]     )     )
      __SCREAMING_SNAKE_CASE   				=							"""B = """ + """ + """.join(
          f"""{coef}*x^{i}""" for coef, i in enumerate(self.polyB[: self.len_B]     )     )
      __SCREAMING_SNAKE_CASE   				=							"""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()









from .imports import is_rich_available


if is_rich_available():
		from rich.traceback import install

		install(show_locals=False)

else:
		raise ModuleNotFoundError('''To use the rich extension, install rich with `pip install rich`''')
