euclid

Euclidean algorithm for Laurent polynomials

Since R2021b

Syntax

dec = euclid(A,B)

Description

dec = euclid(A,B) returns an array of structures such that each row of dec corresponds to the Euclidean division of the Laurent polynomial A by the Laurent polynomial B:

A = B*Q + R,

where Q is the quotient and R is the remainder.

Examples

Euclidean Division of Laurent Polynomials

Create two Laurent polynomials:

• $$A(z)=z^2+3z+5+7z^{-1}$$

• $$B(z)=1+2z^{-1}$$

cfa = [1 3 5 7];
cfb = [1 2];
lpA = laurentPolynomial(Coefficients=cfa,MaxOrder=2);
lpB = laurentPolynomial(Coefficients=cfb);

Perform Euclidean division of $$A(z)$$ by $$B(z)$$. Use the helper function helperPrintLaurent to print the quotient and remainder polynomials of each Euclidean division.

dec = euclid(lpA,lpB);
numFac = size(dec,1);
for k=1:numFac
    q = helperPrintLaurent(dec(k,1).LP);
    r = helperPrintLaurent(dec(k,2).LP);
    fprintf('Euclidean Division #%d\n',k)
    fprintf('Quotient: %s\n',q)
    fprintf('Remainder:  %s\n \n',r)
end

Euclidean Division #1

Quotient: z^(2) + z + 3

Remainder:   + z^(-1)
 

Euclidean Division #2

Quotient: z^(2) + z + 3.5

Remainder:   - 0.5
 

Euclidean Division #3

Quotient: z^(2) + 0.75*z + 3.5

Remainder:   + 0.25*z
 

Euclidean Division #4

Quotient: 1.125*z^(2) + 0.75*z + 3.5

Remainder:  - 0.125*z^(2)
 

For each Euclidean division, confirm that $$A(z)=B(z)Q_i(z)+R_i(z)$$, where $$Q_i(z)$$ and $$R_i(z)$$ are the quotient and remainder polynomials, respectively, of the ith division.

for k=1:numFac
    q = dec(k,1).LP;
    r = dec(k,2).LP;
    areEqual = (lpA==lpB*q+r);
    fprintf('Euclidean Division #%d: %d\n',k,areEqual)
end

Euclidean Division #1: 1
Euclidean Division #2: 1
Euclidean Division #3: 1
Euclidean Division #4: 1

Input Arguments

A — Laurent polynomial

laurentPolynomial object

Laurent polynomial, specified as a laurentPolynomial object.

B — Laurent polynomial

laurentPolynomial object

Laurent polynomial, specified as a laurentPolynomial object.

Output Arguments

dec — Euclidean algorithm factors

structure array

Euclidean algorithm factors, returned as a N-by-2 structure array, where N ≤ 4 is the number of decompositions. The ith row of dec contains one Euclidean division of A by B:

A = B*(dec(i,1).LP) + dec(i,2).LP

where

• dec(i,1).LP is the Laurent polynomial corresponding to the quotient.

• dec(i,2).LP is the Laurent polynomial corresponding to the remainder.

Extended Capabilities

C/C++ Code Generation
Generate C and C++ code using MATLAB® Coder™.

Version History

Introduced in R2021b