Polynomial synthetic division: Difference between revisions
→{{header|jq}}
SqrtNegInf (talk | contribs) m (→{{header|Perl 6}}: corrected hidden precedence bug) |
|||
| (21 intermediate revisions by 14 users not shown) | |||
Line 1:
{{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}}
<
import (
Line 39 ⟶ 341:
Q, R := div(N, D)
fmt.Printf("%v / %v = %v remainder %v\n", N, D, Q, R)
}</
{{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}}==
Line 49 ⟶ 399:
Solving this the easy way:
<
Task example:
<
┌────────┬────┐
│1 _9 _27│_123│
└────────┴────┘
</syntaxhighlight>
=={{header|Java}}==
{{trans|Python}}
<
public class Test {
Line 96 ⟶ 446:
};
}
}</
<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}}
<
fun extendedSyntheticDivision(dividend: IntArray, divisor: IntArray): Pair<IntArray, IntArray> {
Line 131 ⟶ 548:
print("${n2.contentToString()} / ${d2.contentToString()} = ")
println("${q2.contentToString()}, remainder ${r2.contentToString()}")
}</
{{out}}
Line 141 ⟶ 558:
</pre>
=={{header|
<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('
}
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]
=={{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.
{{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):
Line 198 ⟶ 706:
if __name__ == '__main__':
print
N = [1, -12, 0, -42]
D = [1, -3]
print
</syntaxhighlight>
Sample output:
<pre>
POLYNOMIAL SYNTHETIC DIVISION
[1, -12, 0, -42] / [1, -3] = [1, -9, -27] remainder [-123]
</pre>
Line 214 ⟶ 721:
{{trans|Python}}
<
(require racket/list)
;; dividend and divisor are both polynomials, which are here simply lists of coefficients.
Line 247 ⟶ 754:
(define D '(1 -3))
(define-values (Q R) (extended-synthetic-division N D))
(printf "~a / ~a = ~a remainder ~a~%" N D Q R))</
{{out}}
Line 253 ⟶ 760:
<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}}==
<
/* extended to support order of divisor >1 */
call set_dd '1 0 0 0 -1'
Line 324 ⟶ 862:
Return list']'
</syntaxhighlight>
{{out}}
<pre>[1,-12,0,-42] / [1,-3]
Line 335 ⟶ 873:
===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)].
<
object PolynomialSyntheticDivision extends App {
Line 363 ⟶ 901:
}%s")
}</
=={{header|Sidef}}==
{{trans|Python}}
<
var end = divisor.end
var out = dividend.clone
Line 389 ⟶ 928:
var (n, d) = ([1, -12, 0, -42], [1, -3])
print(" %s / %s =" % (n, d))
print(" %s remainder %s\n" % extended_synthetic_division(n, d))</
{{out}}
[1, -12, 0, -42] / [1, -3] = [1, -9, -27] remainder [-123]
Line 398 ⟶ 937:
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>).
<
# start defaults to 0: [range 5] = {0 1 2 3 4}
proc range {a {b ""}} {
Line 447 ⟶ 986:
puts "$top / $btm = $div"
}
test</
{{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}}
<
# 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]
Line 474 ⟶ 1,055:
separator := -(divisor.len() - 1);
return(out[0,separator], out[separator,*]) # return quotient, remainder.
}</
<
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()));</
{{out}}
<pre>
| |||