Given two polynomials - show how multiplication between them is o(nlogm)
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2

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

  1. #1
    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. #2
    Join Date
    Feb 2011
    Location
    United States
    Posts
    1,006

    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
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center