gcdex
-- the extended Euclidean
algorithm for polynomialsgcdex
(p, q, x)
regards p
and
q
as univariate polynomials in x
and returns
their greatest common divisor as a linear combination of p
and q
.
gcdex(p, q <, x>)
gcdex(f, g, x)
p, q |
- | polynomials of type
DOM_POLY |
f, g |
- | polynomial expressions |
x |
- | an indeterminate: an identifier or an indexed identifier |
a sequence of three polynomials, or a sequence of three polynomial
expressions, or FAIL
.
p
, q
factor
, div
, divide
, gcd
, ifactor
, igcd
, igcdex
, ilcm
, lcm
, mod
, poly
gcdex(
p, q, x)
returns a sequence g,
s, t with three elements, where the polynomial g is
the greatest common divisor of p and q. The
polynomials s and t satisfy g = s*p +
t*q and degree(s, x) < degree(q, x), degree(t,
x) < degree(p, x). These data are computed by the extended
Euclidean algorithm.gcdex
only processes univariate polynomials:
x
is specified, the input
polynomials are regarded as univariate polynomials in
x
.x
must be specified if polynomial expressions
are used on input.poly
for details.
FAIL
is returned if an argument cannot be converted to a
polynomial.DOM_POLY
are
returned."_divide"
. This method must return FAIL
if domain elements cannot be
divided.If the coefficient domain of the polynomial is not a field, then it may not be possible to represent a greatest common divisor as a linear combination of the input polynomials. In such a case, an error is raised.
The greatest common divisor of two univariate polynomials in extended form can be computed as follows:
>> gcdex(poly(x^3 + 1), poly(x^2 + 2*x + 1))
poly(x + 1, [x]), poly(1/3, [x]), poly(- 1/3 x + 2/3, [x])
For multivariate polynomials, an indeterminate must be specified:
>> gcdex(poly(x^2*y), poly(x + y), x)
/ 1 \ / / 1 \ 1 \ poly(1, [x]), poly| --, [x] |, poly| | - -- | x + -, [x] | | 3 | | | 2 | y | \ y / \ \ y / /
>> gcdex(poly(x^2*y), poly(x + y), y)
/ 1 \ / 1 \ poly(1, [y]), poly| - --, [y] |, poly| -, [y] | | 3 | \ x / \ x /
>> gcdex(x^3 + a, x^2 + 1, x)
2 a + x 1 - x - a x 1, ------, ------------ 2 2 a + 1 a + 1