Polynomial Long Division

Question

Implement polynomial long division, an algorithm that divides two polynomials and gets the quotient and remainder:

(12x^3 - 5x^2 + 3x - 1) / (x^2 - 5) = 12x - 5 R 63x - 26

In your programs, you will represent polynomials as an array, with the constant term on the tail. for example, x^5 - 3x^4 + 2x^2 - x + 1 will become [1, -3, 0, 2, -1, 1].

The long division function you are going to write will return two values: the quotient and the remainder. You do not need to handle numerical imprecisions and arithmetic errors. Do not use math library to do your job, however, you may make your function able to deal with symbolic values. Shortest code wins.

EXAMPLE: div([12, -5, 3, -1], [1, 0, -5]) == ([12, -5], [63, -26])

Answer 1

J, 94

f=:>@(0&{)
d=:0{[%~0{[:f]
D=:4 :'x((1}.([:f])-((#@]{.[)f)*d);([:>1{]),d)^:(>:((#f y)-(#x)))y'

eg.

(1 0 _5) D (12 _5 3 _1;'')
63 _26 | 12  _5

Explanation of some snippets, given that a: (12 -5 3 -1) and b: (1 0 -5)

length of a:

#a
4

make a and b same order by appending zeroes to b:

(#a) {. b
1 0 -5 0

divide higher powers (first elements) of a, b:

(0{a) % (0{b)
12

multiply b by that and subtract it from a:

a - 12*b
12 0 _60

repeat n times b = f(a,b):

a f^:n b

Answer 2

Python 2, 260 258 257 255 bytes

exec'''def d(p,q):
 R=range;D=len(p);F=len(q)-1;d=q[0];q=[q[i]/-d@R(1,F+1)];r=[0@R(D)];a=[[0@R(F)]@R(D)]
@R(D):
  p[i]/=d;r[i]=sum(a[i])+p[i]
  for j in R(F):
   if i<D-F:a[i+j+1][F-j-1]=r[i]*q[j]
 return r[:D-F],[d*i@r[D-F:]]'''.replace('@',' for i in ')

This executes:

def d(p,q):
 R=range;D=len(p);F=len(q)-1;d=q[0];q=[q[i]/-d for i in R(1,F+1)];r=[0 for i in R(D)];a=[[0 for i in R(F)] for i in R(D)]
 for i in R(D):
  p[i]/=d;r[i]=sum(a[i])+p[i]
  for j in R(F):
   if i<D-F:a[i+j+1][F-j-1]=r[i]*q[j]
 return r[:D-F],[d*i for i in r[D-F:]]

Use like so:

>>>d([12., -5., 3., -1.],[1.,0.,-5.])
([12.0, -5.0], [63.0, -26.0])

Answer 3

Haskell, 126

For a start:

l s _ 0=s
l(x:s)(y:t)n=x/y:l(zipWith(-)s$map(*(x/y))t++repeat 0)(y:t)(n-1)
d s t=splitAt n$l s t n where n=length s-length t+1

Sample use:

*Main> d [12, -5, 3, -1] [1, 0, -5]
([12.0,-5.0],[63.0,-26.0])

Answer 4

Javascript with lambdas, 108

f=(a,b)=>{for(n=b.length;a.length>=n;a.shift())for(b.push(k=a[q=0]/b[0]);q<n;++q)a[q]-=k*b[q];b.splice(0,n)}

It replaces first argument by reminder and second by result.

Example of usage in Firefox:

f(x=[12,-5,3,-1], y=[1,0,-5]), console.log(x, y)
// Array [ 63, -26 ] Array [ 12, -5 ]

Sorry for the bug. Already fixed.

Answer 5

APL (Dyalog Unicode) 18.0, 63 bytes

{0≥d←1+⍺-⍥≢⍵:⍬⍺⋄q(r↓⍨⊥⍨0=⌽r←⍺-m+.×q←(d↑⍺)⌹d↑m←⍉{⍵,⍨⍺⍴0}∘⍵⍤0⍳d)}

Try it online!

The TIO link (which uses 17.1) has a polyfill for ⍥.

Well, it uses ⌹ to solve a system of equations, but technically it's not a library, so...

How it works

Illustration for the inputs x←12 ¯5 3 ¯1 and y←1 0 ¯5:

• We know that, from the lengths of x and y, the quotient will have two terms.
• Construct a matrix which, when matrix-multiplied with the quotient, will give the polynomial product of quotient with y:

 1  0
 0  1
¯5  0
 0 ¯5

• Calculate the quotient q so that first two terms of x agree with those of y×q, using matrix division ⌹.
• Calculate the remainder r using x - y×q, then remove leading zeros of r. (q is guaranteed to have no leading zeros.)

{ ⍝ x←dividend, y←divisor
  d←1+⍺-⍥≢⍵  ⍝ Degree of the quotient; 1 + length of x - length of y
  0≥d: ⍬⍺    ⍝ If degree is zero or lower: quotient is zero, remainder is x

  m←⍉{⍵,⍨⍺⍴0}∘⍵⍤0⍳d  ⍝ Construct the matrix
                 ⍳d  ⍝ 0..d-1
     {      }∘⍵⍤0    ⍝ For each number i, yielding a matrix row
      ⍵,⍨⍺⍴0         ⍝ Make i copies of 0, and append y
                     ⍝ (Implicitly right-pad with zeros for short rows)
    ⍉                ⍝ Transpose

  q←(d↑⍺)⌹d↑m  ⍝ Get the quotient
          d↑m  ⍝ Take first d rows of the matrix
    (d↑⍺)      ⍝ Take first d numbers of x
         ⌹     ⍝ Matrix divide aka. solve linear system of equations

  r←⍺-m+.×q  ⍝ Get the remainder

  q(r↓⍨⊥⍨0=⌽r)  ⍝ Remove leading zeros from r, and join with q
       ⊥⍨0=⌽    ⍝ Reverse r, test equal to zero, and count trailing ones (⊥⍨)
    r↓⍨         ⍝ Drop that many numbers from start of r
  q(         )  ⍝ Join with q
}