GCD of polynomials

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

hi,
anyone knows how does an algorithm for calculating GCD of two polynomials
look like ?

adrin, Jan 5, 2005

2. HowardGuest

Try searching at groups.google.com. It's a great resource!
-Howard

Howard, Jan 5, 2005

i searched google groups, but with no result...

adrin, Jan 5, 2005
4. alvaro.begueGuest

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
5. HowardGuest

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
6. Victor BazarovGuest

V

Victor Bazarov, Jan 5, 2005

wrote in
thank you very much!!
and how does division algorithm look like?

adrin, Jan 5, 2005
8. BusterGuest

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