División larga polinómica

10

Implemente la división larga polinómica, un algoritmo que divide dos polinomios y obtiene el cociente y el resto:

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

En sus programas, representará polinomios como una matriz, con el término constante en la cola. por ejemplo, x ^ 5 - 3x ^ 4 + 2x ^ 2 - x + 1 se convertirá en [1, -3, 0, 2, -1, 1].

La función de división larga que va a escribir devolverá dos valores: el cociente y el resto. No necesita manejar imprecisiones numéricas y errores aritméticos. No use la biblioteca matemática para hacer su trabajo, sin embargo, puede hacer que su función sea capaz de manejar valores simbólicos. El código más corto gana.

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

code-golf math abstract-algebra polynomials Ming-Tang
fuente
rosettacode.org/wiki/Polynomial_synthetic_division#Python
ghosts_in_the_code

Respuestas:

3

J 94

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

p.ej.

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

Explicación de algunos fragmentos, dado que a: (12 -5 3 -1) yb: (1 0 -5)

longitud de a:

#a
4

haga ayb el mismo orden agregando ceros a b:

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

dividir potencias superiores (primeros elementos) de a, b:

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

multiplique b por eso y reste de a:

a - 12*b
12 0 _60

repetir n veces b = f (a, b):

a f^:n b
Eelvex
fuente
Dos cosas. 1) ¿ganas personajes tomando dividendos / divisores en el orden inusual? 2) ¿es necesario ese `` '' final en el dividendo? parece algo que deberías hacer desde el programa real.
JB
@JB: 1) No, en realidad podría ser más corto para el orden "habitual"; es solo la forma en que empecé a pensar en ello. 2) Es parte de la matriz, así que supongo que debería ser parte de la entrada.
Eelvex
Parece que no puedo entender lo que una matriz vacía adicional tiene que ver con la entrada.
JB
3

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

Esto ejecuta:

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 así:

>>>d([12., -5., 3., -1.],[1.,0.,-5.])
([12.0, -5.0], [63.0, -26.0])
Justin
fuente
1
Wow, la primera vez que he visto un ejecutivo / reemplazo en realidad se usa para guardar personajes.
xnor
@xnor Lo he hecho otra vez, pero para más de un reemplazo.
Justin
2

Haskell, 126

Para comenzar:

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

Uso de la muestra:

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

Javascript con 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)}

Reemplaza el primer argumento por recordatorio y el segundo por resultado.

Ejemplo de uso en Firefox:

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

Perdón por el error. Ya está arreglado.

Qwertiy
fuente