The FFT algorithm we described in this lecture is limited to polynomials with 2k coefficients for...

 

Transcribed Image Text:

The FFT algorithm we described in this lecture is limited to polynomials with 2k coefficients for some integer k. Of course, we can always pad the coefficient vector with zeros to force it into this form, but this padding artificially inflates the input size, leading to a slower algorithm than necessary. Describe and analyze a similar DFT algorithm that works for polynomials with 3k coefficients, by splitting the coefficient vector into three smaller vectors of length 3k-1, recursively computing the DFT of each smaller vector, and correctly combining the results. The FFT algorithm we described in this lecture is limited to polynomials with 2k coefficients for some integer k. Of course, we can always pad the coefficient vector with zeros to force it into this form, but this padding artificially inflates the input size, leading to a slower algorithm than necessary. Describe and analyze a similar DFT algorithm that works for polynomials with 3k coefficients, by splitting the coefficient vector into three smaller vectors of length 3k-1, recursively computing the DFT of each smaller vector, and correctly combining the results.

Answer rating: 100% (QA)

Answer Given two polynomial Ax and Bx find the product Cx AxBx There is already an O naive approach to solve this problem here This approach uses the coefficient form of the polynomial to calculate th... View the full answer