Polynomial Greatest Common Divisor

The calculator produces the polynomial greatest common divisor using the Euclid method and polynomial division. The polynomial coefficients are integers, fractions, or complex numbers with integer or fractional real and imaginary parts. The result is polynomial, which divides two input polynomials without remainder or 1 if there is no such polynomial.

Polynomial greatest common divisor.

Polynomial 1

Polynomial 2

PseudoremaindersCommon division Trivial pseudodivision Reducing polynomial content Subresultant PRS Subresultant PRS, Advanced

Pseudoremainders correction algorithm.

Estimate remainders calculation method performance

Coefficients GCD will be calculated on each step.

Calculation precision

Exact

Rounded

Digits after the decimal point: 2

Calculate

Result

 

The file is very large. Browser slowdown may occur during loading and creation.

Download 

 Link  Save  Widget

The phenomenon of explosive coefficient growth.

For calculating GCD for the polynomials of higher degrees, the polynomial remainder coefficients grow explosively. Even in this calculator, you may see it with default input data; the remainder sequence contains big fractions. To eliminate the fractions and reduce integer coefficients, one can use pseudo division with a remainder coefficient reduction algorithm. 3 pseudo remainder calculation algorithms are available in this calculator, not counting trivial pseudo division without any coefficient reduction.

Best coefficient reduction gives content reduction method, which divides all the terms by the coefficients GCD. But the computing cost of this method can be unacceptably high for higher degree polynomials with complex coefficients since the Euclidean algorithm is applied in every iteration for every coefficient.

As the tradeoff variant of coefficient growth controlling is algorithms based on subresultant PRS, The calculator employs two of them (Algorithm 1 and Algorithm 3), described by W.S. Brown in the article: The Subresultant PRS Algorithm¹.
The calculator produces the pseudo remainders table with polynomial content for every remainder to estimate algorithm effectiveness. The lesser content, the higher algorithm effectiveness.