Main Content

euclid

Euclidean algorithm for Laurent polynomials

    Description

    example

    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

    collapse all

    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