Polynomial multiplication using the DFT?
How to do polynomial multiplication using the discrete Fourier transform in SageMath?
How to do polynomial multiplication using the discrete Fourier transform in SageMath?
Here is the example from the article in SageMath:
sage: R.<x> = PolynomialRing(QQ)
sage: f = 1 + x
sage: g = 1 + x + x^2
sage: fg_deg = f.degree() + g.degree()
sage: I_f = IndexedSequence([f.monomial_coefficient(x^d) for d in range(fg_deg+1)], list(range(fg_deg+1)))
sage: I_g = IndexedSequence([g.monomial_coefficient(x^d) for d in range(fg_deg+1)], list(range(fg_deg+1)))
sage: I_fg = IndexedSequence(list(vector(I_f.dft().list()).pairwise_product(vector(I_g.dft().list()))), list(range(fg_deg+1))).idft()
sage: fg = sum(c*x^k for k,c in I_fg.dict().items())
sage: fg == f*g
True
Asked: 2022-03-02 14:47:10 +0200
Seen: 354 times
Last updated: Mar 02 '22
Related: DST and polynomial multiplication.