CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

Thread: Given two polynomials - show how multiplication between them is o(nlogm)

1. Junior Member
Join Date
Dec 2011
Posts
1

Given two polynomials - show how multiplication between them is o(nlogm)

Hi ,

I've two polynomials , one of degree "m" and the other of degree "n" , and I need show how
the multiplication between them is o(n*log(m)) , when m<n .

Let's say , A(x) has degree "n" , and B(x) has degree "m"

My felling is the following :
1. We take the first polynomial , let's call it A(x) , and separate it to "m" parts , meaning m/n polynomials in the total . This would take o(n)

2. Take each one of the broken polynomials and multiply it with B(x) using FFT .

3.We store the result in an array of n+m values .

but from here I don't know how to continue . I'd appreciate your help ,

Regards,Ron

2. Re: Given two polynomials - show how multiplication between them is o(nlogm)

Interesting question. I did not realize a fast FFT-based polynomial multiplication algorithm existed. Perhaps this link will help: http://www.cs.iastate.edu/~cs577/han...lymultiply.pdf

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

Click Here to Expand Forum to Full Width