Find polynomial GCD by "Leading-coefficient Elinimation"


Updated 22 Jan 2018

View License

In the longhand polynomial division given as
P(k) = P(k-2) - P(k-1)*Q(k)
The quotient Q(k) and the remainder P(k) are obtained from dividing the dividend P(k-2) by the divisor P(k-1). If we can make Q(k) = 1, by converting P(k-2) and P(k-1) into equal degree and monic, then the longhand polynomial division becomes simply the "monic polynomial subtraction" (MPS):
P(k) = P(k-2) - P(k-1)
For a pair of given polynomials p(x) and q(x) of degree n and m, n>m, we set
P(1) = p(x)/p_0
P(2) = q(x)*x^(n-m)/q_0
Applying the MPS repeatedly starting from k=3, until k=K+1, such that
P(K+1) = P(k-1) - P(k) = 0
then we get our desired polynomial GCD as
gcd(p,q) = P(K).
The source code uses only basic MATLAB built-in functions. Its listing is only 17 lines total !
Amazingly, this simple routine gives the expected results for the test polynomials and their derivatives of very high degree, such as
p(x) = (x + 1)^1000
p(x) = (x + 123456789)^30
p(x) = (1234x + 56789)^60
p(x) = (x^4-2x^3+3x^2-4x +5)^50
p(x) = (x^4 - 1)^25
*************** UPDATE (10/05/09): **************
The approach "Leading-coefficient Elinimation" is revised from the original "Monic Polynomial Subtraction".
It also reduces almost half of the total arithematic operations.
The total source code listing is only 12 lines!
*************** UPDATE (01/22/2018): **************
The source code function g = poly_gcd(p,q) is revised and updated. It greatly reduces the overall operation procedures.
Please see the typical examples in the comment section.

Cite As

Feng Cheng Chang (2023). poly_gcd(p,q) (https://www.mathworks.com/matlabcentral/fileexchange/20859-poly_gcd-p-q), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R13
Compatible with any release
Platform Compatibility
Windows macOS Linux
Find more on Polynomials in Help Center and MATLAB Answers

Inspired: Polynomials with multiple roots solved

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
Version Published Release Notes

The approach "Leading-coefficient Elinimation" is revised from the original "Monic Polynomial Subtraction". Update the m-file. The total m-file listing is fewer than 15 lines!

The source code function is revised and updated. It reduces the overall operation steps.

Revise the m-file. The source code listing is only 17 lines total !

Update the m-file -- improve the case that the leading coef of given poly is very huge.

Update the m-file.

Update the m-file and the description.

Update m-file to include PRS.