We can summarize the process of polynomial multiplication as follows.

  1. Selection: Select a set of points to represent both our polynomials (the complex -th roots of unity).
  2. Evaluation: Convert the two polynomials from the coefficient representation to the value representation (DFT/FFT).
  3. Multiplication: Multiply element-wise to get the value representation of the product of the polynomials.
  4. Interpolation: Convert the value representation back to the coefficient representation (IDFT/IFFT).

We will now implement all of the steps to perform polynomial multiplication using NumPy's DFT/FFT module. We will start by using the DFT to convert between polynomial representations.

Given a polynomial in its coefficient representation, convert it into a value representation using NumPy's DFT/FFT module.

def coefficients_to_values(coefficients):
"""Returns the value representation of a polynomial
Args:
coefficients (array[complex]): a 1-D array of complex
coefficients of a polynomial with
index i representing the i-th degree coefficient

Returns:
array[complex]: the value representation of the
polynomial
"""
##################
# YOUR CODE HERE #
##################
pass

A = [4, 3, 2, 1]
print(coefficients_to_values(A))

or to submit your code

To interact with codercises, please switch to a larger screen size.

Learning Objectives:

  • Explain the idea behind the Fast Fourier transform (FFT) algorithm.
  • Describe the n-th roots of unity.