View source for Polynomial synthetic division

{{draft task|Classic CS problems and programs}}
{{Wikipedia|Synthetic division}}


:<cite>In algebra, [[wp:Synthetic division|polynomial synthetic division]] is an algorithm for dividing a polynomial by another polynomial of the same or lower degree in an efficient way using a trick involving clever manipulations of coefficients, which results in a lower time complexity than [[polynomial long division]].</cite>
<br><br>

=={{header|11l}}==
{{trans|Python}}

<syntaxhighlight lang="11l">F extended_synthetic_division(dividend, divisor)
   ‘Fast polynomial division by using Extended Synthetic Division. Also works with non-monic polynomials.’
   V out = copy(dividend)
   V normalizer = divisor[0]
   L(i) 0 .< dividend.len - (divisor.len - 1)
      out[i] /= normalizer
      V coef = out[i]
      I coef != 0
         L(j) 1 .< divisor.len
            out[i + j] += -divisor[j] * coef
   V separator = divisor.len - 1
   R (out[0 .< (len)-separator], out[(len)-separator..])

print(‘POLYNOMIAL SYNTHETIC DIVISION’)
V n = [1, -12, 0, -42]
V D = [1, -3]
print(‘  #. / #. =’.format(n, D), end' ‘ ’)
V (a, b) = extended_synthetic_division(n, D)
print(‘#. remainder #.’.format(a, b))</syntaxhighlight>

{{out}}
<pre>
POLYNOMIAL SYNTHETIC DIVISION
  [1, -12, 0, -42] / [1, -3] = [1, -9, -27] remainder [-123]
</pre>

=={{header|C++}}==
{{trans|Java}}
<syntaxhighlight lang="cpp">/*
 * C++ Polynomial Sythetic Division
 * GNU Compile example for filename <synthdiv.cpp>
 * g++ -std=c++11 -o synthdiv synthdiv.cpp
 */

#include <iostream>
#include <vector>
#include <string>
#include <cmath>

/*
 * frmtPolynomial method
 * Returns string for formatted 
 * polynomial from int vector of coefs.
 * String looks like ax^2 + bx + c, 
 * a, b, and c being the integer
 * coefs in the vector.
 */

std::string frmtPolynomial(std::vector<int> polynomial, bool remainder = false)
{
	std::string r = "";

	if (remainder) 
	{
		r = " r: " + std::to_string(polynomial.back());
		polynomial.pop_back();
	}

	std::string formatted = "";
	
	int degree = polynomial.size() - 1;
	int d = degree;

	for (int i : polynomial)
	{
		if (d < degree)
		{
			if (i >= 0) 
			{
				formatted += " + ";
			}
			else
			{
				formatted += " - ";
			}
		}

		formatted += std::to_string(abs(i));

		if (d > 1)
		{
			formatted += "x^" + std::to_string(d);
		}
		else if (d == 1)
		{
			formatted += "x";
		}

		d--;
	}

	return formatted;
}

/*
 * syntheticDiv Method
 * Performs Integer Polynomial Sythetic Division
 * on polynomials expressed as vectors of coefs.
 * Takes int vector param for dividend and 
 * divisor, and returns int vector quotient.
 */

std::vector<int> syntheticDiv(std::vector<int> dividend, std::vector<int> divisor)
{
	std::vector<int> quotient;
	quotient = dividend;

	int normalizer = divisor[0];
	
	for (int i = 0; i < dividend.size() - (divisor.size() - 1); i++)
	{
		quotient[i] /= normalizer;
		int coef = quotient[i];

		if (coef != 0) 
		{
			for (int j = 1; j < divisor.size(); j++)
			{
				quotient[i + j] += -divisor[j] * coef;
			}
        }

	}

	return quotient;
}

/*
 * Example of using the syntheticDiv method
 * and the frmtPolynomial method.
 * Assigns dividend and divisor polynomials:
 * dividend: 1x^3 - 12x^2 + 0x - 42
 * divisor: 1x - 3
 * Outputs both to cout using frmtPolynomial.
 * Printed polynomials look like above format.
 * Processes dividend and divisor in the 
 * syntheticDiv method, returns quotient.
 * Outputs quotient to cout using frmtPolynomial again.
 * quotient: 1x^2 - 9x - 27 r: -123
 */

int main(int argc, char **argv) 
{
	std::vector<int> dividend{ 1, -12, 0, -42};
	std::vector<int> divisor{ 1, -3};

	std::cout << frmtPolynomial(dividend) << "\n";
	std::cout << frmtPolynomial(divisor) << "\n";

	std::vector<int> quotient = syntheticDiv(dividend, divisor);

	std::cout << frmtPolynomial(quotient, true) << "\n";

}
</syntaxhighlight>

=={{header|C sharp|C#}}==
{{trans|Java}}
<syntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
using System.Linq;

namespace SyntheticDivision
{
    class Program
    {
        static (List<int>,List<int>) extendedSyntheticDivision(List<int> dividend, List<int> divisor)
        {
            List<int> output = dividend.ToList();
            int normalizer = divisor[0];

            for (int i = 0; i < dividend.Count() - (divisor.Count() - 1); i++)
            {
                output[i] /= normalizer;

                int coef = output[i];
                if (coef != 0)
                {
                    for (int j = 1; j < divisor.Count(); j++)
                        output[i + j] += -divisor[j] * coef;
                }
            }

            int separator = output.Count() - (divisor.Count() - 1);

            return (
                output.GetRange(0, separator),
                output.GetRange(separator, output.Count() - separator)
            );
        }

        static void Main(string[] args)
        {
            List<int> N = new List<int>{ 1, -12, 0, -42 };
            List<int> D = new List<int> { 1, -3 };

            var (quotient, remainder) = extendedSyntheticDivision(N, D);
            Console.WriteLine("[ {0} ] / [ {1} ] = [ {2} ], remainder [ {3} ]" ,
                string.Join(",", N),
                string.Join(",", D),
                string.Join(",", quotient),
                string.Join(",", remainder)
            );
        }
    }
}
</syntaxhighlight>

=={{header|Delphi}}==
{{libheader| System.SysUtils}}
{{libheader| Velthuis.BigRationals}}
{{Trans|Go}}
Thanks Rudy Velthuis for the [https://github.com/rvelthuis/DelphiBigNumbers  Velthuis.BigRationals] library.<br>
<syntaxhighlight lang="delphi">
program Polynomial_synthetic_division;

{$APPTYPE CONSOLE}

uses
  System.SysUtils,
  Velthuis.BigRationals;

type
  TPollynomy = record
  public
    Terms: TArray<BigRational>;
    class operator Divide(a, b: TPollynomy): TArray<TPollynomy>;
    constructor Create(Terms: TArray<BigRational>);
    function ToString: string;
  end;

{ TPollynomy }

constructor TPollynomy.Create(Terms: TArray<BigRational>);
begin
  self.Terms := copy(Terms, 0, length(Terms));
end;

class operator TPollynomy.Divide(a, b: TPollynomy): TArray<TPollynomy>;
var
  q, r: TPollynomy;
begin
  var o: TArray<BigRational>;
  SetLength(o, length(a.Terms));
  for var i := 0 to High(a.Terms) do
    o[i] := BigRational.Create(a.Terms[i]);

  for var i := 0 to length(a.Terms) - length(b.Terms) do
  begin
    o[i] := BigRational.Create(o[i] div b.Terms[0]);
    var coef := BigRational.Create(o[i]);
    if coef.Sign <> 0 then
    begin
      var aa: BigRational := 0;
      for var j := 1 to High(b.Terms) do
      begin
        aa := (-b.Terms[j]) * coef;
        o[i + j] := o[i + j] + aa;
      end;
    end;
  end;
  var separator := length(o) - (length(b.Terms) - 1);

  q := TPollynomy.Create(copy(o, 0, separator));
  r := TPollynomy.Create(copy(o, separator, length(o)));

  result := [q, r];
end;

function TPollynomy.ToString: string;
begin
  Result := '[';
  for var e in Terms do
    Result := Result + e.ToString + ' ';
  Result := Result + ']';
end;

var
  p1, p2: TPollynomy;

begin
  p1 := TPollynomy.Create([BigRational.Create(1, 1), BigRational.Create(-12, 1),
    BigRational.Create(0, 1), BigRational.Create(-42, 1)]);

  p2 := TPollynomy.Create([BigRational.Create(1, 1), BigRational.Create(-3, 1)]);

  write(p1.ToString, ' / ', p2.ToString, ' = ');

  var result := p1 / p2;
  writeln(result[0].ToString, ' remainder ', result[1].ToString);
  readln;
end.</syntaxhighlight>
{{out}}
<pre>[1 -12 0 -42 ] / [1 -3 ] = [1 -9 -27 ] remainder [-123 ]</pre>


=={{header|Go}}==
{{trans|Python}}
<syntaxhighlight lang="go">package main

import (
    "fmt"
    "math/big"
)

func div(dividend, divisor []*big.Rat) (quotient, remainder []*big.Rat) {
    out := make([]*big.Rat, len(dividend))
    for i, c := range dividend {
        out[i] = new(big.Rat).Set(c)
    }
    for i := 0; i < len(dividend)-(len(divisor)-1); i++ {
        out[i].Quo(out[i], divisor[0])
        if coef := out[i]; coef.Sign() != 0 {
            var a big.Rat
            for j := 1; j < len(divisor); j++ {
                out[i+j].Add(out[i+j], a.Mul(a.Neg(divisor[j]), coef))
            }
        }
    }
    separator := len(out) - (len(divisor) - 1)
    return out[:separator], out[separator:]
}

func main() {
    N := []*big.Rat{
        big.NewRat(1, 1),
        big.NewRat(-12, 1),
        big.NewRat(0, 1),
        big.NewRat(-42, 1)}
    D := []*big.Rat{big.NewRat(1, 1), big.NewRat(-3, 1)}
    Q, R := div(N, D)
    fmt.Printf("%v / %v = %v remainder %v\n", N, D, Q, R)
}</syntaxhighlight>
{{out}}
<pre>
[1/1 -12/1 0/1 -42/1] / [1/1 -3/1] = [1/1 -9/1 -27/1] remainder [-123/1]
</pre>

=={{header|Haskell}}==
<syntaxhighlight lang="haskell">import Data.List

normalized :: (Eq a, Num a) => [a] -> [a]
normalized = dropWhile (== 0)

isZero :: (Eq a, Num a) => [a] -> Bool
isZero = null . normalized

shortDiv :: (Eq a, Fractional a) => [a] -> [a] -> ([a], [a])
shortDiv p1 p2
  | isZero p2 = error "zero divisor"
  | otherwise =
      let go 0 p = p 
          go i (h:t) = (h/a) : go (i-1) (zipWith (+) (map ((h/a) *) ker) t)
      in splitAt k $ go k p1
  where
    k = length p1 - length as
    a:as = normalized p2
    ker = negate <$> (as ++ repeat 0)</syntaxhighlight>

<pre>*Main> shortDiv [1,-12,0,-42] [1,1,-3]
([1.0,-13.0],[16.0,-81.0])

*Main> shortDiv [6,5,0,-7] [3,-2,-1]
([2.0,3.0],[8.0,-4.0])</pre>

For monic divisors it is possible to perform purely integral computations (without Fractional constraint):

<syntaxhighlight lang="haskell">isMonic :: (Eq a, Num a) => [a] -> Bool
isMonic = ([1] ==) . take 1 . normalized

shortDivMonic :: (Eq a, Num a) => [a] -> [a] -> ([a], [a])
shortDivMonic p1 p2
  | isZero p2 = error "zero divisor"
  | not (isMonic p2) = error "divisor is not monic"
  | otherwise = 
      let go 0 p = p 
          go i (h:t) = h : go (i-1) (zipWith (+) (map (h *) ker) t)
      in splitAt k $ go k p1
    where
      k = length p1 - length as
      _:as = normalized p2
      ker = negate <$> as ++ repeat 0</syntaxhighlight>

<pre>shortDivMonic [1,-12,0,-42] [1,1,-3 :: Int]
([1,-13],[16,-81])</pre>

=={{header|J}}==

Solving this the easy way:

<syntaxhighlight lang="j">   psd=: [:(}. ;{.) ([ (] -/@,:&}. (* {:)) ] , %&{.~)^:(>:@-~&#)~</syntaxhighlight>

Task example:

<syntaxhighlight lang="j">   (1, (-12), 0, -42) psd (1, -3)
┌────────┬────┐
│1 _9 _27│_123│
└────────┴────┘
</syntaxhighlight>

=={{header|Java}}==
{{trans|Python}}
<syntaxhighlight lang="java">import java.util.Arrays;

public class Test {

    public static void main(String[] args) {
        int[] N = {1, -12, 0, -42};
        int[] D = {1, -3};

        System.out.printf("%s / %s = %s",
                Arrays.toString(N),
                Arrays.toString(D),
                Arrays.deepToString(extendedSyntheticDivision(N, D)));
    }

    static int[][] extendedSyntheticDivision(int[] dividend, int[] divisor) {
        int[] out = dividend.clone();
        int normalizer = divisor[0];

        for (int i = 0; i < dividend.length - (divisor.length - 1); i++) {
            out[i] /= normalizer;

            int coef = out[i];
            if (coef != 0) {
                for (int j = 1; j < divisor.length; j++)
                    out[i + j] += -divisor[j] * coef;
            }
        }

        int separator = out.length - (divisor.length - 1);

        return new int[][]{
            Arrays.copyOfRange(out, 0, separator),
            Arrays.copyOfRange(out, separator, out.length)
        };
    }
}</syntaxhighlight>

<pre>[1, -12, 0, -42] / [1, -3] = [[1, -9, -27], [-123]]</pre>

=={{header|jq}}==
{{works with|jq}}

'''Works with gojq, the Go implementation of jq'''

'''Works with jaq, the Rust implementation of jq'''

In this entry, the polynomial of degree n, SIGMA c[i] * x^(n-i), is represented by
the JSON array c.
<syntaxhighlight lang="jq">
# Solution: {"quotient", "remainder"}
def extendedSyntheticDivision($dividend; $divisor):
  { out: $dividend,
    normalizer: $divisor[0],
    separator: (($dividend|length) - ($divisor|length) + 1) }
  | reduce range(0; .separator) as $i (.;
      .out[$i] = ((.out[$i] / .normalizer)|trunc)
      | .out[$i] as $coef
      | if $coef != 0
        then reduce range(1; $divisor|length) as $j (.;
          .out[$i + $j] -=  $divisor[$j] * $coef )
        else .
        end )
  | {quotient: .out[0:.separator], remainder: .out[.separator:]} ;

def task($n; $d):
  def r: if length==1 then first else . end;
  extendedSyntheticDivision($n; $d)
  | "\($n) / \($d)  =  \(.quotient), remainder \(.remainder|r)" ;

task([1, -12, 0, -42]; [1, -3]),
task([1, 0, 0, 0, -2];[1, 1, 1, 1])
</syntaxhighlight>
{{output}}
<pre>
[1,-12,0,-42] / [1,-3]  =  [1,-9,-27], remainder -123
[1,0,0,0,-2] / [1,1,1,1]  =  [1,-1], remainder [0,0,-1]
</pre>

=={{header|Julia}}==
{{trans|Perl}}
<syntaxhighlight lang="julia">function divrem(dividend::Vector, divisor::Vector)
    result = copy(dividend)
    quotientlen = length(divisor) - 1
    for i in 1:length(dividend)-quotientlen
        if result[i] != 0
            result[i] /= divisor[1]
            for j in 1:quotientlen
                result[i + j] -= divisor[j + 1] * result[i]
            end
        end
    end
    return result[1:end-quotientlen], result[end-quotientlen+1:end]
end

testpolys = [([1, -12, 0, -42], [1, -3]), ([1, 0, 0, 0, -2], [1, 1, 1, 1])]

for (n, d) in testpolys
    quotient, remainder = divrem(n, d)
    println("[$n] / [$d] = [$quotient] with remainder [$remainder]")
end
</syntaxhighlight>{{out}}
<pre>
[[1, -12, 0, -42]] / [[1, -3]] = [[1, -9, -27]] with remainder [[-123]]
[[1, 0, 0, 0, -2]] / [[1, 1, 1, 1]] = [[1, -1]] with remainder [[0, 0, -1]]
</pre>

=={{header|Kotlin}}==
{{trans|Python}}
<syntaxhighlight lang="scala">// version 1.1.2

fun extendedSyntheticDivision(dividend: IntArray, divisor: IntArray): Pair<IntArray, IntArray> {
    val out = dividend.copyOf()
    val normalizer = divisor[0]
    val separator = dividend.size - divisor.size + 1
    for (i in 0 until separator) {
        out[i] /= normalizer
        val coef = out[i]
        if (coef != 0) { 
            for (j in 1 until divisor.size) out[i + j] += -divisor[j] * coef
        }
    }
    return out.copyOfRange(0, separator) to out.copyOfRange(separator, out.size) 
}

fun main(args: Array<String>) {
    println("POLYNOMIAL SYNTHETIC DIVISION")
    val n = intArrayOf(1, -12, 0, -42)
    val d = intArrayOf(1, -3)
    val (q, r) = extendedSyntheticDivision(n, d)
    print("${n.contentToString()} / ${d.contentToString()}  =  ")
    println("${q.contentToString()}, remainder ${r.contentToString()}")
    println()
    val n2 = intArrayOf(1, 0, 0, 0, -2)
    val d2 = intArrayOf(1, 1, 1, 1)
    val (q2, r2) = extendedSyntheticDivision(n2, d2)
    print("${n2.contentToString()} / ${d2.contentToString()}  =  ")
    println("${q2.contentToString()}, remainder ${r2.contentToString()}")
}</syntaxhighlight>

{{out}}
<pre>
POLYNOMIAL SYNTHETIC DIVISION
[1, -12, 0, -42] / [1, -3]  =  [1, -9, -27], remainder [-123]

[1, 0, 0, 0, -2] / [1, 1, 1, 1]  =  [1, -1], remainder [0, 0, -1]
</pre>

=={{header|Mathematica}} / {{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">MakePolynomial[l_List, x_] := FromCoefficientRules[Thread[List /@ Range[Length[l] - 1, 0, -1] -> l], {x}]
num = MakePolynomial[{1, -12, 0, -42}, x];
den = MakePolynomial[{1, -3}, x];
PolynomialQuotient[num, den, x]
PolynomialRemainder[num, den, x]</syntaxhighlight>
{{out}}
<pre>-27 - 9 x + x^2
-123</pre>

=={{header|Nim}}==
{{trans|Kotlin}}
<syntaxhighlight lang="nim">import strformat

type Polynomial = seq[int]

func `$`(p: Polynomial): string = system.`$`(p)[1..^1]

func extendedSyntheticDivision(dividend, divisor: Polynomial): tuple[q, r: Polynomial] =
    var res = dividend
    let normalizer = divisor[0]
    let separator = dividend.len - divisor.len
    for i in 0..separator:
      res[i] = res[i] div normalizer
      let coef = res[i]
      if coef != 0:
        for j in 1..divisor.high:
          res[i + j] += -divisor[j] * coef
    result = (res[0..separator], res[(separator+1)..^1])

when isMainModule:
  echo "Polynomial synthetic division"
  let n1 = @[1, -12, 0, -42]
  let d1 = @[1, -3]
  let (q1, r1) = extendedSyntheticDivision(n1, d1)
  echo &"{n1} / {d1}  =  {q1}, remainder {r1}"
  let n2 = @[1, 0, 0, 0, -2]
  let d2 = @[1, 1, 1, 1]
  let (q2, r2) = extendedSyntheticDivision(n2, d2)
  echo &"{n2} / {d2}  =  {q2}, remainder {r2}"</syntaxhighlight>

{{out}}
<pre>Polynomial synthetic division
[1, -12, 0, -42] / [1, -3]  =  [1, -9, -27], remainder [-123]
[1, 0, 0, 0, -2] / [1, 1, 1, 1]  =  [1, -1], remainder [0, 0, -1]</pre>

=={{header|Perl}}==
{{trans|Raku}}
<syntaxhighlight lang="perl">sub synthetic_division {
    my($numerator,$denominator) = @_;
    my @result = @$numerator;
    my $end    = @$denominator-1;

    for my $i (0 .. @$numerator-($end+1)) {
        next unless $result[$i];
        $result[$i]    /= @$denominator[0];
        $result[$i+$_] -= @$denominator[$_] * $result[$i] for 1 .. $end;
    }

    return join(' ', @result[0 .. @result-($end+1)]), join(' ', @result[-$end .. -1]);
}

sub poly_divide {
    *n = shift; *d = shift;
    my($quotient,$remainder)= synthetic_division( \@n, \@d );
    "[@n] / [@d] = [$quotient], remainder [$remainder]\n";
}

print poly_divide([1, -12, 0, -42], [1, -3]);
print poly_divide([1, 0, 0, 0, -2], [1, 1, 1, 1]);</syntaxhighlight>
{{out}}
<pre>[1 -12 0 -42] / [1 -3] = [1 -9 -27], remainder [-123]
[1 0 0 0 -2] / [1 1 1 1] = [1 -1], remainder [0 0 -1]</pre>

=={{header|Phix}}==
{{trans|Kotlin}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
 <span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
 <span style="color: #008080;">function</span> <span style="color: #000000;">extendedSyntheticDivision</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">dividend</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">divisor</span><span style="color: #0000FF;">)</span>
     <span style="color: #004080;">sequence</span> <span style="color: #000000;">out</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dividend</span><span style="color: #0000FF;">)</span>
     <span style="color: #004080;">integer</span> <span style="color: #000000;">normalizer</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">divisor</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span>
             <span style="color: #000000;">separator</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dividend</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">-</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">divisor</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span>
     <span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">separator</span> <span style="color: #008080;">do</span>
         <span style="color: #000000;">out</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">/=</span> <span style="color: #000000;">normalizer</span>
         <span style="color: #004080;">integer</span> <span style="color: #000000;">coef</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">out</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
         <span style="color: #008080;">if</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">coef</span> <span style="color: #0000FF;">!=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
             <span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">divisor</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
                 <span style="color: #004080;">integer</span> <span style="color: #000000;">odx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">j</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
                 <span style="color: #000000;">out</span><span style="color: #0000FF;">[</span><span style="color: #000000;">odx</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">divisor</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">coef</span>
             <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
         <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
     <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
     <span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">out</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">separator</span><span style="color: #0000FF;">],</span><span style="color: #000000;">out</span><span style="color: #0000FF;">[</span><span style="color: #000000;">separator</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..$]}</span>
 <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
  
 <span style="color: #008080;">constant</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">42</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">3</span><span style="color: #0000FF;">}},</span>
                   <span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">42</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">3</span><span style="color: #0000FF;">}},</span>
                   <span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">}},</span>
                   <span style="color: #0000FF;">{{</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">7</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}}}</span>
  
 <span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Polynomial synthetic division\n"</span><span style="color: #0000FF;">)</span>
 <span style="color: #008080;">for</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
     <span style="color: #004080;">sequence</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">t</span><span style="color: #0000FF;">],</span>
              <span style="color: #0000FF;">{</span><span style="color: #000000;">q</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">extendedSyntheticDivision</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">)</span>
     <span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%v / %v  =  %v, remainder %v\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #000000;">q</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">})</span>
 <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Polynomial synthetic division
{1,-12,0,-42} / {1,-3}  =  {1,-9,-27}, remainder {-123}
{1,-12,0,-42} / {1,1,-3}  =  {1,-13}, remainder {16,-81}
{1,0,0,0,-2} / {1,1,1,1}  =  {1,-1}, remainder {0,0,-1}
{6,5,0,-7} / {3,-2,-1}  =  {2,3}, remainder {8,-4}
</pre>

=={{header|Python}}==
Here is an extended synthetic division algorithm, which means that it supports a divisor polynomial (instead of just a monomial/binomial). It also supports non-monic polynomials (polynomials which first coefficient is different than 1). Polynomials are represented by lists of coefficients with decreasing degree (left-most is the major degree , right-most is the constant).
{{works with|Python 2.7}}
{{works with|Python 3.x}}
<syntaxhighlight lang="python">from __future__ import print_function
from __future__ import division

#!/usr/bin/python
# coding=UTF-8

def 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 = list(dividend) # Copy the dividend
    normalizer = divisor[0]
    for i in xrange(len(dividend)-(len(divisor)-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
            for j in xrange(1, len(divisor)): # in synthetic division, we always skip the first coefficient of the divisor,
                                              # because it's only used to normalize the dividend coefficients
                out[i + j] += -divisor[j] * coef

    # The resulting out contains both the quotient and the 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 = -(len(divisor)-1)
    return out[:separator], out[separator:] # return quotient, remainder.

if __name__ == '__main__':
    print("POLYNOMIAL SYNTHETIC DIVISION")
    N = [1, -12, 0, -42]
    D = [1, -3]
    print("  %s / %s  =" % (N,D), " %s remainder %s" % extended_synthetic_division(N, D))
</syntaxhighlight>

Sample output:
<pre>
POLYNOMIAL SYNTHETIC DIVISION
  [1, -12, 0, -42] / [1, -3]  =  [1, -9, -27] remainder [-123]
</pre>

=={{header|Racket}}==
{{trans|Python}}

<syntaxhighlight lang="racket">#lang racket/base
(require racket/list)
;; dividend and divisor are both polynomials, which are here simply lists of coefficients.
;; Eg: x^2 + 3x + 5 will be represented as (list 1 3 5)
(define (extended-synthetic-division dividend divisor)
  (define out (list->vector dividend)) ; Copy the dividend
  ;; for general polynomial division (when polynomials are non-monic), we need to normalize by
  ;; dividing the coefficient with the divisor's first coefficient
  (define normaliser (car divisor))
  (define divisor-length (length divisor)) ; } we use these often enough
  (define out-length (vector-length out))  ; }
  
  (for ((i (in-range 0 (- out-length divisor-length -1))))
    (vector-set! out i (quotient (vector-ref out i) normaliser))
    (define coef (vector-ref out i))
    (unless (zero? coef) ; useless to multiply if coef is 0
      (for ((i+j (in-range (+ i 1)                ; in synthetic division, we always skip the first
                           (+ i divisor-length))) ; coefficient of the divisior, because it's
            (divisor_j (in-list (cdr divisor))))  ;  only used to normalize the dividend coefficients
        (vector-set! out i+j (+ (vector-ref out i+j) (* coef divisor_j -1))))))
  ;; The resulting out contains both the quotient and the 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.

  ;; return quotient, remainder (conveniently like quotient/remainder)
  (split-at (vector->list out) (- out-length (sub1 divisor-length))))

(module+ main
  (displayln "POLYNOMIAL SYNTHETIC DIVISION")
  (define N '(1 -12 0 -42))
  (define D '(1 -3))
  (define-values (Q R) (extended-synthetic-division N D))
  (printf "~a / ~a = ~a remainder ~a~%" N D Q R))</syntaxhighlight>

{{out}}

<pre>POLYNOMIAL SYNTHETIC DIVISION
(1 -12 0 -42) / (1 -3) = (1 -9 -27) remainder (-123)</pre>

=={{header|Raku}}==
(formerly Perl 6)
{{trans|Python}}
{{works with|Rakudo|2018.09}}

<syntaxhighlight lang="raku" line>sub synthetic-division ( @numerator, @denominator ) {
    my @result = @numerator;
    my $end    = @denominator.end;

    for ^(@numerator-$end) -> $i {
        @result[$i]    /= @denominator[0];
        @result[$i+$_] -= @denominator[$_] * @result[$i] for 1..$end;
    }

    'quotient' => @result[0 ..^ *-$end],
    'remainder' => @result[*-$end .. *];
}

my @tests =
[1, -12, 0, -42], [1, -3],
[1, 0, 0, 0, -2], [1, 1, 1, 1];

for @tests -> @n, @d {
    my %result = synthetic-division( @n, @d );
    say "[{@n}] / [{@d}] = [%result<quotient>], remainder [%result<remainder>]";
}</syntaxhighlight>
{{out}}
<pre>[1 -12 0 -42] / [1 -3] = [1 -9 -27], remainder [-123] 
[1 0 0 0 -2] / [1 1 1 1] = [1 -1], remainder [0 0 -1] 
</pre>

=={{header|REXX}}==
<syntaxhighlight lang="rexx">/* REXX Polynomial Division                */
/* extended to support order of divisor >1 */
call set_dd '1 0 0 0 -1'
Call set_dr '1 1 1 1'
Call set_dd '1 -12 0 -42'
Call set_dr '1 -3'
q.0=0
Say list_dd '/' list_dr
do While dd.0>=dr.0
  q=dd.1/dr.1
  Do j=1 To dr.0
    dd.j=dd.j-q*dr.j
    End
  Call set_q q
  Call shift_dd
  End
say 'Quotient:' mk_list_q() 'Remainder:' mk_list_dd()
Exit

set_dd:
Parse Arg list
list_dd='['
Do i=1 To words(list)
  dd.i=word(list,i)
  list_dd=list_dd||dd.i','
  End
dd.0=i-1
list_dd=left(list_dd,length(list_dd)-1)']'
Return

set_dr:
Parse Arg list
list_dr='['
Do i=1 To words(list)
  dr.i=word(list,i)
  list_dr=list_dr||dr.i','
  End
dr.0=i-1
list_dr=left(list_dr,length(list_dr)-1)']'
Return

set_q:
z=q.0+1
q.z=arg(1)
q.0=z
Return

shift_dd:
Do i=2 To dd.0
  ia=i-1
  dd.ia=dd.i
  End
dd.0=dd.0-1
Return

mk_list_q:
list='['q.1''
Do i=2 To q.0
  list=list','q.i
  End
Return list']'

mk_list_dd:
list='['dd.1''
Do i=2 To dd.0
  list=list','dd.i
  End
Return list']'

</syntaxhighlight>
{{out}}
<pre>[1,-12,0,-42] / [1,-3]
Quotient: [1,-9,-27] Remainder: -123

[1,0,0,0,-2] / [1,1,1,1]
Quotient: [1,-1] Remainder: [0,0,-1]</pre>

=={{header|Scala}}==
===Java Interoperability===
{{Out}}Best seen running in your browser either by [https://scalafiddle.io/sf/59vpjcQ/0 ScalaFiddle (ES aka JavaScript, non JVM)] or [https://scastie.scala-lang.org/uUk8yRPnQdGdS1aAUFjhmA Scastie (remote JVM)].
<syntaxhighlight lang="scala">import java.util

object PolynomialSyntheticDivision extends App {

  val N: Array[Int] = Array(1, -12, 0, -42)
  val D: Array[Int] = Array(1, -3)

  def extendedSyntheticDivision(dividend: Array[Int],
                                divisor: Array[Int]): Array[Array[Int]] = {
    val out = dividend.clone
    val normalizer = divisor(0)

    for (i <- 0 until dividend.length - (divisor.length - 1)) {
      out(i) /= normalizer
      val coef = out(i)
      if (coef != 0)
        for (j <- 1 until divisor.length) out(i + j) += -divisor(j) * coef
    }
    val separator = out.length - (divisor.length - 1)
    Array[Array[Int]](util.Arrays.copyOfRange(out, 0, separator),
      util.Arrays.copyOfRange(out, separator, out.length))
  }

  println(f"${util.Arrays.toString(N)}%s / ${util.Arrays.toString(D)}%s = ${
    util.Arrays
      .deepToString(extendedSyntheticDivision(N, D).asInstanceOf[Array[AnyRef]])
  }%s")

}</syntaxhighlight>

=={{header|Sidef}}==
{{trans|Python}}
<syntaxhighlight lang="ruby">func extended_synthetic_division(dividend, divisor) {
    var end = divisor.end
    var out = dividend.clone
    var normalizer = divisor[0]

    for i in ^(dividend.len - end) {
        out[i] /= normalizer
        var coef = out[i]
        if (coef != 0) {
            for j in (1 .. end) {
                out[i+j] += -(divisor[j] * coef)
            }
        }
    }

    var remainder = out.splice(-end)
    var quotient = out

    return(quotient, remainder)
}

var (n, d) = ([1, -12, 0, -42], [1, -3])
print("  %s / %s =" % (n, d))
print(" %s remainder %s\n" % extended_synthetic_division(n, d))</syntaxhighlight>
{{out}}
  [1, -12, 0, -42] / [1, -3] = [1, -9, -27] remainder [-123]

=={{header|Tcl}}==
{{trans|Python}}

This uses a common utility proc <tt>range</tt>, and a less common one called <tt>lincr</tt>, which increments elements of lists.  The routine for polynomial division is placed in a namespace ensemble, such that it can be conveniently shared with other commands for polynomial arithmetic (eg <tt>polynomial multiply</tt>).

<syntaxhighlight lang="tcl">#   range ?start? end+1
# start defaults to 0:  [range 5] = {0 1 2 3 4}
proc range {a {b ""}} {
    if {$b eq ""} {
        set b $a
        set a 0
    }
    for {set r {}} {$a<$b} {incr a} {
        lappend r $a
    }
    return $r
}

#   lincr list idx ?...? increment
# By analogy with [lset] and [incr]:
# Adds incr to the item at [lindex list idx ?...?].  incr may be a float.
proc lincr {_ls args} {
    upvar 1 $_ls ls
    set incr [lindex $args end]
    set idxs [lrange $args 0 end-1]
    lset ls {*}$idxs [expr {$incr + [lindex $ls {*}$idxs]}]
}

namespace eval polynomial {
    # polynomial division, returns [list $dividend $remainder]
    proc divide {top btm} {
        set out $top
        set norm [lindex $btm 0]
        foreach i [range [expr {[llength $top] - [llength $btm] + 1}]] {
            lset out $i [set coef [expr {[lindex $out $i] * 1.0 / $norm}]]
            if {$coef != 0} {
                foreach j [range 1 [llength $btm]] {
                    lincr out [expr {$i+$j}] [expr {-[lindex $btm $j] * $coef}]
                }
            }
        }
        set terms [expr {[llength $btm]-1}]
        list [lrange $out 0 end-$terms] [lrange $out end-[incr terms -1] end]
    }
    namespace export *
    namespace ensemble create
}

proc test {} {
    set top {1 -12 0 -42}
    set btm {1 -3}
    set div [polynomial divide $top $btm]
    puts "$top / $btm = $div"
}
test</syntaxhighlight>

{{out}}
<pre>1 -12 0 -42 / 1 -3 = {1.0 -9.0 -27.0} -123.0</pre>

=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-dynamic}}
<syntaxhighlight lang="wren">import "./dynamic" for Tuple

var Solution = Tuple.create("Solution", ["quotient", "remainder"])

var extendedSyntheticDivision = Fn.new { |dividend, divisor|
    var out = dividend.toList
    var normalizer = divisor[0]
    var separator = dividend.count - divisor.count + 1
    for (i in 0...separator) {
        out[i] = (out[i] / normalizer).truncate
        var coef = out[i]
        if (coef != 0) {
            for (j in 1...divisor.count) out[i + j] = out[i + j] - divisor[j] * coef
        }
    }
    return Solution.new(out[0...separator], out[separator..-1])
}

System.print("POLYNOMIAL SYNTHETIC DIVISION")
var n = [1, -12, 0, -42]
var d = [1, -3]
var sol = extendedSyntheticDivision.call(n, d)
System.write("%(n) / %(d)  =  ")
System.print("%(sol.quotient), remainder %(sol.remainder)")
System.print()
var n2 = [1, 0, 0, 0, -2]
var d2 = [1, 1, 1, 1]
var sol2 = extendedSyntheticDivision.call(n2, d2)
System.write("%(n2) / %(d2)  =  ")
System.print("%(sol2.quotient), remainder %(sol2.remainder)")</syntaxhighlight>

{{out}}
<pre>
POLYNOMIAL SYNTHETIC DIVISION
[1, -12, 0, -42] / [1, -3]  =  [1, -9, -27], remainder [-123]

[1, 0, 0, 0, -2] / [1, 1, 1, 1]  =  [1, -1], remainder [0, 0, -1]
</pre>

=={{header|zkl}}==
{{trans|Python}}
<syntaxhighlight 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.
}</syntaxhighlight>
<syntaxhighlight 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()));</syntaxhighlight>
{{out}}
<pre>
POLYNOMIAL SYNTHETIC DIVISION
  L(1,-12,0,-42) / L(1,-3) = L(1,-9,-27) remainder L(-123)
</pre>