-
December 14th, 2011, 03:01 AM
#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
-
December 14th, 2011, 03:48 AM
#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
Best Regards,
BioPhysEngr
http://blog.biophysengr.net
--
All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|