Code covered by the BSD License

### Highlights from GCD of Polynomials

5.0
5.0 | 1 rating Rate this file 13 Downloads (last 30 days) File Size: 1.32 KB File ID: #20859 Version: 1.8

# GCD of Polynomials

### Feng Cheng Chang (view profile)

26 Jul 2008 (Updated )

Find polynomial GCD by "Leading-coefficient Elinimation"

File Information
Description

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!

Acknowledgements

This file inspired Polynomials With Multiple Roots Solved.

MATLAB release MATLAB 6.5 (R13)
29 Nov 2009 Feng Cheng Chang

### Feng Cheng Chang (view profile)

Pozos:
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
r=x*p+y*q.
In addition, we may also find the two polynomials t and s, so that
1=u/t+v/s, or
r=p/t+q/s.
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

Comment only
24 Nov 2009 bullpoz Pozos

### bullpoz Pozos (view profile)

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:
r=xp+ψq
if you understand can you tell me how to show this expression out of the gcd code
Thanks

Comment only
14 Nov 2009 Feng Cheng Chang

### Feng Cheng Chang (view profile)

Pozos:
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

Comment only
09 Nov 2009 bullpoz Pozos

### bullpoz Pozos (view profile)

11 Aug 2008

Update the M-file. Add "Polynomial remainder sequences" as output.

04 Jan 2009 1.1

Update the m-file and the description.

12 Apr 2009 1.2

Update the m-file.

14 Jun 2009 1.3

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

11 Aug 2009 1.4

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

06 Oct 2009 1.8

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!