Polynomial synthetic division: Difference between revisions

</pre>

=={{header|zkl}}==

{{trans|Python}}

<lang zkl>fcn extended_synthetic_division(dividend, divisor){

# Fast polynomial division by using Extended Synthetic Division. Also works with non-monic polynomials.

# dividend and divisor are both polynomials, which are here simply lists of coefficients. Eg: x^2 + 3x + 5 will be represented as [1, 3, 5]

out,normalizer:=dividend.copy(), divisor[0];

foreach i in (dividend.len() - (divisor.len() - 1)){

out[i] /= normalizer; # for general polynomial division (when polynomials are non-monic),

# we need to normalize by dividing the coefficient with the divisor's first coefficient

coef := out[i];

if(coef != 0){ # useless to multiply if coef is 0

foreach j in ([1..divisor.len() - 1]){ # in synthetic division, we always skip the first coefficient of the divisior,

out[i + j] += -divisor[j] * coef; # because it's only used to normalize the dividend coefficients

}

}

}

# out contains the quotient and remainder, the remainder being the size of the divisor (the remainder

# has necessarily the same degree as the divisor since it's what we couldn't divide from the dividend), so we compute the index

# where this separation is, and return the quotient and remainder.

separator := -(divisor.len() - 1);

return(out[0,separator], out[separator,*]) # return quotient, remainder.

}</lang>

<lang zkl>println("POLYNOMIAL SYNTHETIC DIVISION");

N,D := T(1, -12, 0, -42), T(1, -3);

print(" %s / %s =".fmt(N,D));

println(" %s remainder %s".fmt(extended_synthetic_division(N,D).xplode()));</lang>

{{out}}

<pre>

POLYNOMIAL SYNTHETIC DIVISION

L(1,-12,0,-42) / L(1,-3) = L(1,-9,-27) remainder L(-123)