Polynomial long division: Difference between revisions

* Error handling (for allocations or for wrong inputs) is not mandatory.

* Conventions can be different; in particular, note that if the first coefficient in the vector is the highest power of x for the polynomial represented by the vector, then the algorithm becomes simpler.

 

'''Example for clarification'''

q: -27 -9 1 → x² - 9x - 27

r: -123 0 0 → -123

 

=={{header|Ada}}==

long_division.adb:

 

procedure Long_Division is

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

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

 

output:

Q: x^2 + -9*x + -27

R: -123</pre>

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

 

{{trans|Java}}

 

namespace PolynomialLongDivision {

}

}

{{out}}

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

Quotient : x^2 - 9.0x - 27.0

Remainder : -123.0</pre>

 

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

 

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

[1, 3, 2] / [1, 1] => [1.0, 2.0] remainder [0.0]

[1, -4, 6, 5, 3] / [1, 2, 1] => [1.0, -6.0, 17.0] remainder [-23.0, -14.0]

</pre>

 

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

 

implicit none

 

end subroutine poly_print

 

 

use Polynom

implicit none

deallocate(q, r)

 

 

=={{header|Go}}==

By the convention and pseudocode given in the task:

 

import "fmt"

}

return q, nn, true

Output:

<pre>

R: [-123 0 0 0]

</pre>

 

=={{header|Haskell}}==

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:

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

 

=={{header|Java}}==

 

public class PolynomialLongDivision {

 

}

 

}

 

}

}

}

 

}

}

 

}

}

 

}

}

}

}

 

}

}

}

}

}

}

}

 

}

{{out}}

 

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

typealias IAE = IllegalArgumentException

data class Solution(val quotient: DoubleArray, val remainder: DoubleArray)

fun polyDegree(p: DoubleArray): Int {

for (i in p.size - 1 downTo 0) {

return Int.MIN_VALUE

}

fun polyShiftRight(p: DoubleArray, places: Int): DoubleArray {

if (places <= 0) return p

return d

}

fun polyMultiply(p: DoubleArray, m: Double) {

for (i in 0 until p.size) p[i] *= m

}

fun polySubtract(p: DoubleArray, s: DoubleArray) {

for (i in 0 until p.size) p[i] -= s[i]

}

fun polyLongDiv(n: DoubleArray, d: DoubleArray): Solution {

if (n.size != d.size) {

return Solution(q, n2)

}

fun polyShow(p: DoubleArray) {

val pd = polyDegree(p)

println()

}

fun main(args: Array<String>) {

val n = doubleArrayOf(-42.0, 0.0, -12.0, 1.0)

print("Remainder : ")

polyShow(r)

 

{{out}}

<pre>

Numerator : x^3 - 12.0x^2 - 42.0

Denominator : x - 3.0

Quotient : x^2 - 9.0x - 27.0

Remainder : -123.0

</pre>

 

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

 

output:

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

 

=={{header|OCaml}}==

 

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

 

 

for i=length(p) to 1 by -1 do

if p[i]!=0 then return i end if

return -1

end function

function poly_div(sequence n, d)

while length(d)<length(n) do d &=0 end while

integer dn = degree(n),

dd = degree(d)

if dd<0 then throw("divide by zero") end if

while dn>=dd do

sequence d2 = d[1..length(d)-k]

for i=1 to length(d2) do

end for

end while

end function

function poly(sequence si)

string r = ""

for t=length(si) to 1 by -1 do

return r

end function

constant tests = {{{-42,0,-12,1},{-3,1}},

{{-3,1},{-42,0,-12,1}},

{{-56,87,-94,-55,22,-7},{2,0,1}},

}

constant fmt = "%40s / %-16s = %25s rem %s\n"

for i=1 to length(tests) do

{{out}}

x^3 - 12x^2 - 42 / x - 3 = x^2 - 9x - 27 rem -123

x - 3 / x^3 - 12x^2 - 42 = 0 rem x - 3

 

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

 

def degree(poly):

mult = q[dN - dD] = N[-1] / float(d[-1])

d = [coeff*mult for coeff in d]

dN = degree(N)

r = N

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

Remainder: -123 </pre>

 

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

 

 

=={{header|Tcl}}==

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

<-2.700000e+01,-9.000000e+00,1.000000e+00>,

<-1.230000e+02>)</pre>

 

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