Polynomial synthetic division: Difference between revisions

{{trans|Python}}

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

V out = copy(dividend)

print(‘ #. / #. =’.format(n, D), end' ‘ ’)

V (a, b) = extended_synthetic_division(n, D)

{{out}}

=={{header|C++}}==

{{trans|Java}}

* C++ Polynomial Sythetic Division

* GNU Compile example for filename <synthdiv.cpp>

}

=={{header|C sharp|C#}}==

{{trans|Java}}

using System.Collections.Generic;

using System.Linq;

}

}

=={{header|Delphi}}==

{{Trans|Go}}

Thanks Rudy Velthuis for the [https://github.com/rvelthuis/DelphiBigNumbers Velthuis.BigRationals] library.<br>

program Polynomial_synthetic_division;

writeln(result[0].ToString, ' remainder ', result[1].ToString);

readln;

{{out}}

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

=={{header|Go}}==

{{trans|Python}}

import (

Q, R := div(N, D)

fmt.Printf("%v / %v = %v remainder %v\n", N, D, Q, R)

{{out}}

<pre>

=={{header|Haskell}}==

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

k = length p1 - length as

a:as = normalized p2

<pre>*Main> shortDiv [1,-12,0,-42] [1,1,-3]

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

isMonic = ([1] ==) . take 1 . normalized

k = length p1 - length as

_:as = normalized p2

<pre>shortDivMonic [1,-12,0,-42] [1,1,-3 :: Int]

Solving this the easy way:

Task example:

┌────────┬────┐

│1 _9 _27│_123│

└────────┴────┘

=={{header|Java}}==

{{trans|Python}}

public class Test {

};

}

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

=={{header|Julia}}==

{{trans|Perl}}

result = copy(dividend)

quotientlen = length(divisor) - 1

println("[$n] / [$d] = [$quotient] with remainder [$remainder]")

end

<pre>

[[1, -12, 0, -42]] / [[1, -3]] = [[1, -9, -27]] with remainder [[-123]]

=={{header|Kotlin}}==

{{trans|Python}}

fun extendedSyntheticDivision(dividend: IntArray, divisor: IntArray): Pair<IntArray, IntArray> {

print("${n2.contentToString()} / ${d2.contentToString()} = ")

println("${q2.contentToString()}, remainder ${r2.contentToString()}")

{{out}}

=={{header|Mathematica}} / {{header|Wolfram Language}}==

num = MakePolynomial[{1, -12, 0, -42}, x];

den = MakePolynomial[{1, -3}, x];

PolynomialQuotient[num, den, x]

{{out}}

<pre>-27 - 9 x + x^2

=={{header|Nim}}==

{{trans|Kotlin}}

type Polynomial = seq[int]

let d2 = @[1, 1, 1, 1]

let (q2, r2) = extendedSyntheticDivision(n2, d2)

{{out}}

=={{header|Perl}}==

{{trans|Raku}}

my($numerator,$denominator) = @_;

my @result = @$numerator;

print poly_divide([1, -12, 0, -42], [1, -3]);

{{out}}

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

=={{header|Phix}}==

{{trans|Kotlin}}

<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: #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>

{{out}}

<pre>

{{works with|Python 2.7}}

{{works with|Python 3.x}}

from __future__ import division

D = [1, -3]

print(" %s / %s =" % (N,D), " %s remainder %s" % extended_synthetic_division(N, D))

Sample output:

{{trans|Python}}

(require racket/list)

;; dividend and divisor are both polynomials, which are here simply lists of coefficients.

(define D '(1 -3))

(define-values (Q R) (extended-synthetic-division N D))

{{out}}

{{works with|Rakudo|2018.09}}

my @result = @numerator;

my $end = @denominator.end;

my %result = synthetic-division( @n, @d );

say "[{@n}] / [{@d}] = [%result<quotient>], remainder [%result<remainder>]";

{{out}}

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

=={{header|REXX}}==

/* extended to support order of divisor >1 */

call set_dd '1 0 0 0 -1'

Return list']'

{{out}}

<pre>[1,-12,0,-42] / [1,-3]

===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 {

}%s")

=={{header|Sidef}}==

{{trans|Python}}

var end = divisor.end

var out = dividend.clone

var (n, d) = ([1, -12, 0, -42], [1, -3])

print(" %s / %s =" % (n, d))

{{out}}

[1, -12, 0, -42] / [1, -3] = [1, -9, -27] remainder [-123]

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 ""}} {

puts "$top / $btm = $div"

}

{{out}}

{{trans|Kotlin}}

{{libheader|Wren-dynamic}}

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

var sol2 = extendedSyntheticDivision.call(n2, d2)

System.write("%(n2) / %(d2) = ")

{{out}}

=={{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]

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));

{{out}}

<pre>