Inverter localmente um polinômio

20

Desafio

Dado um polinômio pcom coeficientes reais de ordem 1e grau n, encontre outro polinômio qde grau no máximo ntal que (p∘q)(X) = p(q(X)) ≡ X mod X^(n+1), ou seja, p(q(X)) = X + h(X)ondeh seja um polinômio arbitrário ord(h) ≥ n+1. O polinômio qé determinado exclusivamente por p.

Para um polinômio p(X) = a(n)*X^n + a(n+1)*X^(n+1) + ... + a(m)*X^monde n <= me a(n) ≠ 0, a(m) ≠ 0dizemos que né a ordem de pe mé o grau de p.

Simplificação : você pode assumir que ppossui coeficientes inteiros e a(1)=1(so p(X) = X + [some integral polynomial of order 2]). Neste caso, também qtem coeficientes integrais.

O objetivo dessa simplificação é evitar os problemas com números de ponto flutuante. Existe, no entanto, um exemplo não integral para fins ilustrativos.

Exemplos

  • Considere a série de Taylor exp(x)-1 = x + x^2/2 + x^3/6 + x^4/24 + ...e ln(x+1) = x - x^2/2 + x^3/3 - x^4/4 + ...então obviamente ln(exp(x)-1+1)= x. Se considerarmos apenas os polinómios de Taylor de grau 4 dessas duas funções que obtemos com a notação de baixo (veja testcases) p = [-1/4,1/3,-1/2,1,0]e q = [1/24, 1/6, 1/2, 1,0]e(p∘q)(X) ≡ X mod X^5

  • Considere o polinômio p(X) = X + X^2 + X^3 + X^4. Então, para q(X) = X - X^2 + X^3 - X^4chegarmos

    (p∘q)(X) = p(q(X)) = X - 2X^5 + 3X^6 - 10X^7 +...+ X^16 ≡ X mod X^5

Casos de teste

Aqui, os polinômios de entrada e saída são escritos como listas de coeficientes (com o coeficiente do mais alto grau monomial primeiro, o termo constante último):

p = [4,3,2,0];  q=[0.3125,-.375,0.5,0]

Casos de teste integrais:

p = [1,0]; q = [1,0]

p = [9,8,7,6,5,4,3,2,1,0]; q = [4862,-1430,429,-132,42,-14,5,-2,1,0]

p = [-1,3,-3,1,0]; q = [91,15,3,1,0]
code-golf math polynomials flawr
fonte

Respostas:

5

Python 2 + sympy, 128 bytes

Invertemos localmente o polinômio assumindo que q (x) = x, compondo-o com p, verificando o coeficiente de x 2 e subtraindo-o de q. Digamos que o coeficiente seja 4, então o novo polinômio se torna q (x) = x - 4x 2 . Em seguida, compomos isso com p, mas procuramos o coeficiente para x 3 . Etc ...

from sympy import*
i=input()
p=Poly(i,var('x'));q=p*0+x
n=2
for _ in i[2:]:q-=compose(p,q).nth(n)*x**n;n+=1
print q.all_coeffs()
orlp
fonte
2

Mathematica, 45 bytes

Normal@InverseSeries[#+O@x^(#~Exponent~x+1)]&

Sim, o Mathematica tem um builtin para isso ....

Função sem nome, tendo como entrada um polinômio na variável x, como -x^4+3x^3-3x^2+xno último caso de teste, e retornando um polinômio com sintaxe semelhante, comox+3x^2+15x^3+91x^4 no último caso de teste.

#+O@x^(#~Exponent~x+1)transforma a entrada #em um objeto de série de potência, truncado no grau de #; InverseSeriesfaz o que diz; e Normaltransforma a série de energia truncada resultante novamente em um polinômio. (Poderíamos salvar esses 7 bytes iniciais se uma resposta no formulário x+3x^2+15x^3+91x^4+O[x]^5fosse aceitável. De fato, se esse fosse um formato aceitável para entrada e saída, então InverseSeriesseria uma solução de 13 bytes.)

Greg Martin
fonte
2

JavaScript (ES6), 138 bytes

a=>a.reduce((r,_,i)=>[...r,i<2?i:a.map(l=>c=p.map((m,j)=>(r.map((n,k)=>p[k+=j]=m*n+(p[k]||0)),m*l+(c[j]||0)),p=[]),c=[],p=[1])&&-c[i]],[])

Porta da resposta do @ orlp. AE / S está na forma de matrizes de coeficientes na ordem inversa, ou seja, os dois primeiros coeficientes são sempre 0 e 1.

Neil
fonte