File Exchange

image thumbnail


version (600 Bytes) by Feng Cheng Chang
Find polynomial GCD by "Leading-coefficient Elinimation"


Updated 22 Jan 2018

View Version History

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 (2021). poly_gcd(p,q) (, MATLAB Central File Exchange. Retrieved .

Comments and Ratings (5)

Feng Cheng Chang

Typical Examples:

Ex. 1,

p = poly([1 1 1 1 -2 -2 -2 -3 -3 4]); q = polyder(p),
p =
1 4 -17 -86 19 376 25 -734 100 600 -288
q =
10 36 -136 -602 114 1880 100 -2202 200 600

g = poly_gcd(p,q)
g =
1 4 -2 -16 5 20 -12

Ex. 2,

p = [225075 0 0 0 0 -20295], q = [88555 0 0 0 -12920],
p =
225075 0 0 0 0 -20295
q =
88555 0 0 0 -12920

g = poly_gcd(p,q)
g =
1 -0.61803

*** Refer to "Polynomial GCDs by Linear Algebra", Notes by Barry Dayton, March 2004. ***

Feng Cheng Chang

To answer your question, first find r the GCD of two given polynomials p and q, then, u=p/r, v=q/r and w=u*v.
The partial fraction expansion (PFE) of 1/w will give 1/w=y/u+x/v,
where the two desired polynomials x and y can thus be determined after performing reverse PFE. Thus,
1 = x*u+y*v, or
In addition, we may also find the two polynomials t and s, so that
1=u/t+v/s, or
It is interesting to note that x and y are expected to be, respectively, equal to 1/t and 1/s. However, it isn't so !
Please let me know if you want find out more detail derivation about these relations.
FC Chang

bullpoz Pozos

FC Chang:
I would like a favor.I've made a gui that represents the gcd
it is like this: r=poly_gcd(p,q)
i've been asked to make this:
if you understand can you tell me how to show this expression out of the gcd code

Feng Cheng Chang

I do not understand your question. But if you means that you want make a gui from my article, you may go ahead to do so.
Please see my other articles, such as "Solve multiple-root polynomials' that may refer computation of polynomial GCD.
FC Chang

bullpoz Pozos

Who can i make a gui of that?please help!

MATLAB Release Compatibility
Created with R13
Compatible with any release
Platform Compatibility
Windows macOS Linux

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!