Ask Your Question
1

Polynomial multiplication using the DFT?

asked 2022-03-02 14:47:10 +0100

rburing gravatar image
edit retag flag offensive close merge delete

Comments

rburing gravatar imagerburing ( 2022-03-02 14:54:30 +0100 )edit

1 Answer

Sort by ยป oldest newest most voted
1

answered 2022-03-02 14:48:16 +0100

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
edit flag offensive delete link more

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: 2022-03-02 14:47:10 +0100

Seen: 410 times

Last updated: Mar 02 '22