CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2
  1. #1
    Join Date
    Dec 2011

    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 ,


  2. #2
    Join Date
    Feb 2011
    United States

    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,

    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

Windows Mobile Development Center

Click Here to Expand Forum to Full Width

On-Demand Webinars (sponsored)

We have made updates to our Privacy Policy to reflect the implementation of the General Data Protection Regulation.