10
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Two things. 1) do you win characters by taking dividend/divisor in the unusual order? 2) is that trailing `;''' in the dividend necessary? looks like something you should do from inside the actual program. \$\endgroup\$ – J B Feb 11 '11 at 23:50
  • \$\begingroup\$ @J-B: 1) No, actually it could be shorter for the "usual" order; it's just the way I started thinking about it. 2) It's part of the array so I suppose it should be part of the input. \$\endgroup\$ – Eelvex Feb 11 '11 at 23:57
  • \$\begingroup\$ I can't seem to grasp what an additional empty array has to do with the input. \$\endgroup\$ – J B Feb 12 '11 at 8:48
2
\$\begingroup\$

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])
\$\endgroup\$
2
\$\begingroup\$

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])
\$\endgroup\$
  • \$\begingroup\$ Wow, first time I've seen an exec/replace actually be used to save characters. \$\endgroup\$ – xnor Oct 27 '14 at 6:15
  • \$\begingroup\$ @xnor I've done that one other time, but for more than one replacement. \$\endgroup\$ – Justin Oct 27 '14 at 6:16
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.