Main Content

euclid

Euclidean algorithm for Laurent polynomials

Since R2021b

collapse all in page

    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.

    example

    Examples

    collapse all

    Open Live Script

    Create two Laurent polynomials:

    • A(z)=z2+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)Qi(z)+Ri(z), where Qi(z) and Ri(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

    collapse all

    Laurent polynomial, specified as a laurentPolynomial object.

    Laurent polynomial, specified as a laurentPolynomial object.

    Output Arguments

    collapse all

    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

    See Also

    Objects