First time here? Check out the FAQ!

Ask Your Question
1

Polynomial multiplication using the DFT?

asked 2 years ago

rburing gravatar image
Preview: (hide)

Comments

rburing gravatar imagerburing ( 2 years ago )

1 Answer

Sort by » oldest newest most voted
1

answered 2 years ago

rburing gravatar image

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
Preview: (hide)
link

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2 years ago

Seen: 439 times

Last updated: Mar 02 '22