0

I am a computer science student, I am studying the Algorithms course independently.

During the course I saw this question:

Multiply the polynomials 1 − 4x − 3x^2 and 2 − 5x using the DFT algorithm. (That is, evaluate the polynomials on the appropriate roots of unity, find the values of the product polynomial on these, and interpolate to obtain its coefficients. Do not use the recursive version, FFT.)

my solution:

For convenience I will mark:

A(x) = 1 − 4x − 3x^2 , B(x) = 2 − 5x

i know that i need to Evaluate A(x) and B(x) at 2n points ω.

i dont sure which ω's use to it.

that i need to obtain the values of A(x)B(x) at these 2n points.

then i need to interpolate the polynomial A · B at the product values using inverse DFT to obtain coefficients c0, c1, . . . , c2n−2.

if i mark A(x) as [1,-4,-3,0] and B(x) as [2,-5,0,0] , i will use 2n complex roots of unity, i.e., ω0,ω1,ω2, . . . , ω2n−1

dust
  • 666
  • 1
  • 4
  • 15
  • 1
    what is the question/problem? see [multiply polynomials with FFT](https://stackoverflow.com/a/22474892/2521214) no need for specific roots of unity nor omega ... or is that related to [NTT](https://stackoverflow.com/q/18577076/2521214) ? but in such case there is still no angle ... however you would limit your polynomial to integer coefficients – Spektre Mar 29 '22 at 10:17

0 Answers0