GCD of polynomials

Discussion in 'C++' started by adrin, Jan 5, 2005.

  1. adrin

    adrin Guest

    hi,
    anyone knows how does an algorithm for calculating GCD of two polynomials
    look like ?
    please help me if you can, or give some relevant links :)
     
    adrin, Jan 5, 2005
    #1
    1. Advertisements

  2. adrin

    Howard Guest

    Try searching at groups.google.com. It's a great resource!
    -Howard
     
    Howard, Jan 5, 2005
    #2
    1. Advertisements

  3. adrin

    adrin Guest

    i searched google groups, but with no result...
    please help me
     
    adrin, Jan 5, 2005
    #3
  4. adrin

    alvaro.begue Guest

    It looks just like Euclid's algorithm. Divide the largest by the
    smallest and replace the largest with the remainder. When the remainder
    is 0, the smallest is the gcd.
     
    alvaro.begue, Jan 5, 2005
    #4
  5. adrin

    Howard Guest

    This isn't the correct forum for finding algorithms...this forum discusses
    C++ language issues. You might look in a newsgroup with the word
    "algorithm" in its name. But, I just did a google search using the
    string"algorithm compute GCD polynomials C++", and got lots of hits that
    looked useful to me.

    -Howard
     
    Howard, Jan 5, 2005
    #5

  6. V
     
    Victor Bazarov, Jan 5, 2005
    #6
  7. adrin

    adrin Guest

    wrote in
    thank you very much!! :)
    and how does division algorithm look like?
     
    adrin, Jan 5, 2005
    #7
  8. adrin

    Buster Guest

    It's long division. Unless the denominator's degree n is less than the
    degree m of the numerator, you can obtain from the denominator a
    polynomial of degree < n by subtracting a scalar multiple of x^(n-m)
    times the numerator. Repeat until the 'denominator' is zero or has
    degree < m. The scalars are the coefficients of x^(n-m) in the quotient,
    and the final 'denominator' is the remainder.
     
    Buster, Jan 6, 2005
    #8
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.