# poly_gcd(p,q)

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 (2024). poly_gcd(p,q) (https://www.mathworks.com/matlabcentral/fileexchange/20859-poly_gcd-p-q), MATLAB Central File Exchange. Retrieved .

##### MATLAB Release Compatibility

##### Platform Compatibility

Windows macOS Linux##### Categories

- MATLAB > Mathematics > Elementary Math > Polynomials >

##### Tags

##### Acknowledgements

**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!### Discover Live Editor

Create scripts with code, output, and formatted text in a single executable document.

Version | Published | Release Notes | |
---|---|---|---|

1.8.0.0 | 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. |
||

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

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

1.2.0.0 | Update the m-file. |
||

1.1.0.0 | Update the m-file and the description. |
||

1.0.0.0 | Update m-file to include PRS. |