Polynomial long division: Difference between revisions

{{trans|Python}}

 

L !poly.empty & poly.last == 0

poly.pop()

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

V (q, r) = poly_div(&n, &D)

 

{{out}}

=={{header|Ada}}==

long_division.adb:

 

procedure Long_Division is

Put ("Q: "); Output (Test_Q);

Put ("R: "); Output (Test_R);

 

output:

 

=={{header|APL}}==

{

q r d←⍵

} ⍬ ⍺ ⍵

}

{{out}}

<pre> N←¯42 0 ¯12 1

 

=={{header|BBC BASIC}}==

DIM D%(3) : D%() = -3, 1, 0, 0

DIM q%(3), r%(3)

IF n%<0 THEN = " - " + STR$(-n%)

IF n%=1 THEN = " + "

'''Output:'''

<pre>

 

{{libheader|GNU Scientific Library}}

#include <stdlib.h>

#include <stdarg.h>

 

return r;

 

{

int i;

 

return 0;

 

===Another version===

#include <stdlib.h>

#include <stdarg.h>

 

return 0;

 

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

{{trans|Java}}

 

namespace PolynomialLongDivision {

}

}

{{out}}

<pre>Numerator : x^3 - 12.0x^2 - 42.0

 

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

#include <iostream>

#include <iterator>

}

 

 

=={{header|Clojure}}==

Since this algorithm is much more efficient when the input is in [https://en.wikipedia.org/wiki/Monomial_order#Graded_reverse_lexicographic_order graded reverse lexicographic (grevlex) order] a comparator is included to be used with Clojure's sorted-map&mdash;<code>(into (sorted-map-by grevlex) ...)</code>&mdash;as well as necessary functions to compute polynomial multiplication, monomial complements, and S-polynomials.

 

(let [grade1 (reduce +' term1)

grade2 (reduce +' term2)

(is (= (divide {[1 1] 2, [1 0] 10, [0 1] 3, [0 0] 15}

{[1 0] 2, [0 0] 3})

 

=={{header|Common Lisp}}==

Polynomials are represented as lists of degree/coefficient pairs ordered by degree (highest degree first), and pairs with zero coefficients can be omitted. <code>Multiply</code> and <code>divide</code> perform long multiplication and long division, respectively. <code>multiply</code> returns one value, the product, and <code>divide</code> returns two, the quotient and the remainder.

 

(do ((sum '())) ((and (endp p1) (endp p2)) (nreverse sum))

(let ((pd1 (if (endp p1) -1 (caar p1)))

(if (endp quotient) (return (values sum remainder))

(setf dividend remainder

 

The [[wp:Polynomial_long_division#Example|wikipedia example]]:

 

'((1 . 1) (0 . -3))) ; x - 3

((2 . 1) (1 . -9) (0 . -27)) ; x^2 - 9x - 27

 

=={{header|D}}==

 

Tuple!(double[], double[]) polyDiv(in double[] inN, in double[] inD)

immutable D = [-3.0, 1.0, 0.0, 0.0];

writefln("%s / %s = %s remainder %s", N, D, polyDiv(N, D)[]);

{{out}}

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

{{libheader| System.SysUtils}}

{{Trans|C#}}

program Polynomial_long_division;

 

FreeMem(Solution, sizeof(TPolySolution));

Readln;

 

=={{header|E}}==

}</pre>

 

def d := makePolynomial([-3, 1])

println("Numerator: ", n)

def [q, r] := n.quotRem(d, stdout)

println("Quotient: ", q)

 

Output:

=={{header|Elixir}}==

{{trans|Ruby}}

def division(_, []), do: raise ArgumentError, "denominator is zero"

def division(_, [0]), do: raise ArgumentError, "denominator is zero"

{q, r} = Polynomial.division(f, g)

IO.puts "#{inspect f} / #{inspect g} => #{inspect q} remainder #{inspect r}"

 

{{out}}

=={{header|F_Sharp|F#}}==

{{trans|Ocaml}}

let rec shift n l = if n <= 0 then l else shift (n-1) (l @ [0.0])

let rec pad n l = if n <= 0 then l else pad (n-1) (0.0 :: l)

" (%s) div (%s)\ngives\nquotient:\t(%s)\nremainder:\t(%s)\n"

(str_poly f) (str_poly g) (str_poly q) (str_poly r)

{{out}}

<pre>

</pre>

=={{header|Factor}}==

 

{{out}}

<pre>

{{works with|Fortran|95 and later}}

 

implicit none

 

end subroutine poly_print

 

 

use Polynom

implicit none

deallocate(q, r)

 

 

=={{Header|FreeBASIC}}==

 

type polyterm

 

poly_print Q() 'quotient

{{out}}

<pre>x^2 - 9x - 27

=={{header|GAP}}==

GAP has built-in functions for computations with polynomials.

p := x^11 + 3*x^8 + 7*x^2 + 3;

q := x^7 + 5*x^3 + 1;

QuotientRemainder(p, q);

 

=={{header|Go}}==

By the convention and pseudocode given in the task:

 

import "fmt"

}

return q, nn, true

Output:

<pre>

Translated from the OCaml code elsewhere on the page.

{{works with|GHC|6.10}}

 

shift n l = l ++ replicate n 0

ks = map (* k) $ shift ddif s

q' = zipWith' (+) q $ shift ddif [k]

 

And this is the also-translated pretty printing function.

 

where term v 0 = show v

term 1 1 = "x"

terms [] = []

terms (0:t) = terms t

 

=={{header|J}}==

From http://www.jsoftware.com/jwiki/Phrases/Polynomials

 

 

Wikipedia example:

This produces the result:

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

<br><br>

To test and validate the results, polynomial multiplication and addition are also implemented.

import java.math.BigInteger;

import java.util.ArrayList;

}

}

{{out}}

<pre>

=={{header|Julia}}==

This task is straightforward with the help of Julia's [https://github.com/Keno/Polynomials.jl Polynomials] package.

using Polynomials

 

 

println(p, " divided by ", q, " is ", d, " with remainder ", r, ".")

 

{{out}}

=={{header|Kotlin}}==

===Version 1===

typealias IAE = IllegalArgumentException

print("Remainder : ")

polyShow(r)

 

{{out}}

===Version 2===

More succinct version that provides an easy-to-use API.

 

operator fun div(divisor: Polynom): Pair<Polynom, Polynom> {

 

print("$num / $den = $quot remainder $rem")

 

{{out}}

=={{header|Maple}}==

As Maple is a symbolic computation system, polynomial arithmetic is, of course, provided by the language runtime. The remainder (rem) and quotient (quo) operations each allow for the other to be computed simultaneously by passing an unassigned name as an optional fourth argument. Since rem and quo deal also with multivariate polynomials, the indeterminate is passed as the third argument.

> p := randpoly( x ); # pick a random polynomial in x

5 4 3 2

> expand( (x^2+2)*q + r - p ); # check

0

 

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

output:

<pre>{-27 - 9 x + x^2, -123}</pre>

 

=={{header|Nim}}==

 

type

echo "D = ", D

echo "q = ", q

 

{{out}}

 

First define some utility operations on polynomials as lists (with highest power coefficient first).

let rec pad n l = if n <= 0 then l else pad (pred n) (0.0 :: l)

let rec norm = function | 0.0 :: tl -> norm tl | x -> x

let zip op p q =

let d = (List.length p) - (List.length q) in

Then the main polynomial division function

let rec aux f s q =

let ddif = (deg f) - (deg s) in

and f' = norm (List.tl (zip (-.) f ks)) in

aux f' s q' in

For output we need a pretty-printing function

let term v p = match (v, p) with

| ( _, 0) -> string_of_float v

| h :: t ->

if h = 0.0 then (terms t) else (term h (List.length t)) :: (terms t) in

and then the example

let f = [1.0; -4.0; 6.0; 5.0; 3.0] and g = [1.0; 2.0; 1.0] in

let q, r = polydiv f g in

Printf.printf

" (%s) div (%s)\ngives\nquotient:\t(%s)\nremainder:\t(%s)\n"

gives the output:

<pre>

Octave has already facilities to divide two polynomials (<code>deconv(n,d)</code>); and the reason to adopt the convention of keeping the highest power coefficient first, is to make the code compatible with builtin functions: we can use <tt>polyout</tt> to output the result.

 

gd = length(d);

pv = zeros(1, length(n));

[q, r] = poly_long_div([1,3], [1,-12,0,-42]);

polyout(q, 'x');

 

=={{header|PARI/GP}}==

This uses the built-in PARI polynomials.

my(rem=a%b);

[(a - rem)/b, rem]

};

Alternately, use the built-in function <code>divrem</code>:

 

=={{header|Perl}}==

 

{{trans|Octave}}

use List::Util qw(min);

 

return ( [0], $rn );

}

 

{

my @c = @_;

}

print "\n";

 

 

($q, $r) = poly_long_div([1, -12, 0, -42], [1, -3]);

($q, $r) = poly_long_div([1,-4,6,5,3], [1,2,1]);

poly_print(@$q);

 

=={{header|Phix}}==

<span style="color: #000080;font-style:italic;">-- demo\rosetta\Polynomial_long_division.exw</span>

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</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: #000000;">fmt</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">({</span><span style="color: #000000;">num</span><span style="color: #0000FF;">,</span><span style="color: #000000;">den</span><span style="color: #0000FF;">,</span><span style="color: #000000;">quo</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rem</span><span style="color: #0000FF;">},</span><span style="color: #000000;">poly</span><span style="color: #0000FF;">))</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

{{out}}

<pre>

 

=={{header|PicoLisp}}==

(let I NIL

(for (N . C) P

(set (nth Q (inc Diff)) F)

(setq N (mapcar '((N E) (- N (* E F))) N E)) ) ) )

Output:

<pre>: (divPoly (-42 0 -12 1) (-3 1 0 0))

=={{header|Python}}==

{{works with|Python 2.x}}

 

from itertools import izip

D = [-3, 1, 0, 0]

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

 

Sample output:

=={{header|R}}==

{{trans|Octave}}

gd <- length(d)

pv <- vector("numeric", length(n))

r <- polylongdiv(c(1,-12,0,-42), c(1,-3))

print.polynomial(r$q)

 

=={{header|Racket}}==

#lang racket

(define (deg p)

'#(-27 -9 1)

'#(-123 0)

 

=={{header|Raku}}==

{{Works with|rakudo|2018.10}}

{{trans|Perl}} for the core algorithm; original code for LaTeX pretty-printing.

return [0], |@n if +@n < +@d;

 

printf Q"%s , & %s \\\\\n", poly_long_div( @a, @b ).map: { poly_print($_) };

}

 

Output:

 

=={{header|REXX}}==

z='1 -12 0 -42' /* Numerator */

n='1 -3' /* Denominator */

d=d-1

End

{{out}}

<pre>(x**3-12*x**2-42)/(x-3)=(x**2-9*x-27)

=={{header|Ruby}}==

Implementing the algorithm given in the task description:

dd = degree(denominator)

raise ArgumentError, "denominator is zero" if dd < 0

q, r = polynomial_long_division(f, g)

puts "#{f} / #{g} => #{q} remainder #{r}"

 

Implementing the algorithms on the [[wp:Polynomial long division|wikipedia page]] -- uglier code but nicer user interface

if g.length == 0 or (g.length == 1 and g[0] == 0)

raise ArgumentError, "denominator is zero"

q, r = polynomial_division(f, g)

puts "#{f} / #{g} => #{q} remainder #{r}"

 

Best of both worlds: {{trans|Tcl}}

if g.length == 0 or (g.length == 1 and g[0] == 0)

raise ArgumentError, "denominator is zero"

q, r = polynomial_division(f, g)

puts "#{f} / #{g} => #{q} remainder #{r}"

 

=={{header|Sidef}}==

{{trans|Perl}}

 

var n = rn.map{_}

 

return([0], rn)

 

Example:

 

var l = c.len

c.each_kv {|i, n|

poly_print(r)

print "\n"

 

{{out}}

=={{header|Slate}}==

 

 

p@(Polynomial traits) new &capacity: n

{q. n}]

ifFalse: [{p newFrom: #(0). p copy}]

 

=={{header|Smalltalk}}==

{{works with|GNU Smalltalk}}

 

|coeffs|

Polynomial class >> new [ ^ super basicNew init ]

]

displayNl [ self display. Character nl display ]

 

res := OrderedCollection new.

 

res do: [ :o |

(o at: 1) display. ' with rest: ' display. (o at: 2) displayNl

 

=={{header|SPAD}}==

{{works with|OpenAxiom}}

{{works with|Axiom}}

 

2

(1) [quotient = x - 9x - 27,remainder = - 123]

 

 

Domain:[http://fricas.github.io/api/PolynomialCategory.html#l-polynomial-category-monic-divide]

{{trans|Kotlin}}

 

static func / (lhs: Self, rhs: Self) -> Self

}

polyPrint(sol.quotient)

print("Remainder: ", terminator: "")

 

{{out}}

{{works with|Tcl|8.5 and later}}

 

# Result is a list of two polynomials, q and r, where n = qd + r

# and the degree of r is less than the degree of b.

lassign [poldiv {-42. 0. -12. 1.} {-3. 1. 0. 0.}] Q R

puts [list Q = $Q]

 

=={{header|Ursala}}==

of the algorithm in terms of list operations (fold, zip, map, distribute, etc.) instead

of array indexing, hence not unnecessarily verbose.

#import flo

 

@lrrPX ==!| zipp0.; @x not zeroid+ ==@h->hr ~&t,

(^lryPX/~&lrrl2C minus^*p/~&rrr times*lrlPD)^/div@bzPrrPlXO ~&,

test program:

 

output:

<pre>(

 

=={{header|VBA}}==

Function degree(p As Variant)

For i = UBound(p) To 1 Step -1

Debug.Print polyn(Array(num, denom, quot, rmdr))

Next i

<pre> x3 - 12x2 - 42 / x - 3 = x2 - 9x - 27 rem -123

x - 3 / x3 - 12x2 - 42 = 0 rem x - 3

===Version 1===

{{libheader|Wren-dynamic}}

 

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

polyShow.call(sol.quotient)

System.write("Remainder : ")

 

{{out}}

 

===Version 2===

construct new(factors) {

_factors = factors.toList

var quot = res[0]

var rem = res[1]

 

{{out}}

 

=={{header|zkl}}==

_assert_(degree(b)>=0,"degree(%s) < 0".fmt(b));

q:=List.createLong(a.len(),0.0);

if(str[0]=="+") str[1,*]; // leave leading space

else String("-",str[2,*]);

println("Quotient = ",polyString(q));

{{out}}

<pre>