Evaluación polinómica

El método de Horner evalúa un polinomio utilizando corchetes repetidos: $${\displaystyle {\begin{aligned}a_{0}+&a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n}\\&=a_{0}+x{\bigg (}a_{1}+x{\Big (}a_{2}+x{\big (}a_{3}+\cdots +x(a_{n-1}+x\,a_{n})\cdots {\big )}{\Big )}{\bigg )}.\end{aligned}}}$$ Este método reduce el número de multiplicaciones y sumas a solo${\displaystyle n}$

El método de Horner es tan común que la " operación de multiplicación y acumulación " está incluida en el conjunto de instrucciones de muchos procesadores informáticos, lo que permite realizar las operaciones de suma y multiplicación en un solo paso combinado.

Los polinomios arbitrarios pueden evaluarse con menos operaciones de las que requiere la regla de Horner si primero "preprocesamos" los coeficientes.${\displaystyle a_{n},\dots ,a_{0}}$.

Un ejemplo fue dado por primera vez por Motzkin ^{[ 3 ]} quien señaló que

${\displaystyle P(x)=x^{4}+a_{3}x^{3}+a_{2}x^{2}+a_{1}x+a_{0}}$

se puede escribir como

${\displaystyle y=(x+\beta _{0})x+\beta _{1},\quad P(x)=(y+x+\beta _{2})y+\beta _{3},}$

donde los valores${\displaystyle \beta _{0},\dots ,\beta _{3}}$se calculan por adelantado, en función de${\displaystyle a_{0},\dots ,a_{3}}$El método de Motzkin utiliza solo 3 multiplicaciones en comparación con las 4 de Horner.

Los valores para cada${\displaystyle \beta _{i}}$se puede calcular fácilmente expandiendo${\displaystyle P(x)}$y igualando los coeficientes:

${\displaystyle {\begin{aligned}\beta _{0}&={\tfrac {1}{2}}(a_{3}-1),\quad &z&=a_{2}-\beta _{0}(\beta _{0}+1),\quad &\beta _{1}&=a_{1}-\beta _{0}z,\\\beta _{2}&=z-2\beta _{1},\quad &\beta _{3}&=a_{0}-\beta _{1}(\beta _{1}+\beta _{2}).\end{aligned}}}$

Evaluación de un polinomio de grado n${\displaystyle P(x)}$en múltiples puntos${\displaystyle x_{1},\dots ,x_{m}}$se puede hacer con${\displaystyle mn}$multiplicaciones utilizando el método de Horner${\displaystyle m}$veces. Utilizando el enfoque de preprocesamiento anterior, esto se puede reducir a la mitad; es decir, a${\displaystyle mn/2}$multiplicaciones.

Sin embargo, es posible hacerlo mejor y reducir el tiempo requerido a solo${\displaystyle O{\big (}(n+m)\log ^{2}(n+m){\big )}}$. ^{[ 5 ]} La idea es definir dos polinomios que sean cero en la primera y segunda mitad de los puntos respectivamente:${\displaystyle m_{0}(x)=(x-x_{1})\cdots (x-x_{n/2})}$y${\displaystyle m_{1}(x)=(x-x_{n/2+1})\cdots (x-x_{n})}$Luego calculamos${\displaystyle R_{0}=P{\bmod {m}}_{0}}$y${\displaystyle R_{1}=P{\bmod {m}}_{1}}$utilizando el teorema del resto de polinomios , que se puede realizar en${\displaystyle O(n\log n)}$tiempo usando una transformada rápida de Fourier . Esto significa${\displaystyle P(x)=Q_{0}(x)m_{0}(x)+R_{0}(x)}$y${\displaystyle P(x)=Q_{1}(x)m_{1}(x)+R_{1}(x)}$por construcción, donde${\displaystyle R_{0}}$y${\displaystyle R_{1}}$son polinomios de grado como máximo${\displaystyle n/2}$. Debido a cómo${\displaystyle m_{0}}$y${\displaystyle m_{1}}$fueron definidos, tenemos

${\displaystyle {\begin{aligned}R_{0}(x_{i})&=P(x_{i})\quad {\text{for }}i\leq n/2\quad {\text{and}}\\R_{1}(x_{i})&=P(x_{i})\quad {\text{for }}i>n/2.\end{aligned}}}$

Por lo tanto, para calcular${\displaystyle P}$en todos${\displaystyle n}$del${\displaystyle x_{i}}$, basta con calcular los polinomios más pequeños${\displaystyle R_{0}}$y${\displaystyle R_{1}}$en cada mitad de los puntos. Esto nos da un algoritmo de divide y vencerás con${\displaystyle T(n)=2T(n/2)+n\log n}$, lo cual implica${\displaystyle T(n)=O(n(\log n)^{2})}$por el teorema maestro .

En el caso de que los puntos en los que deseamos evaluar los polinomios tengan alguna estructura, existen métodos más sencillos. Por ejemplo, Knuth ^{[ 6 ]} sección 4.6.4 proporciona un método para tabular valores polinómicos del tipo

${\displaystyle P(x_{0}+h),P(x_{0}+2h),\dots .}$

En el caso donde${\displaystyle x_{1},\dots ,x_{m}}$no se conocen de antemano, Kedlaya y Umans ^{[ 7 ]} dieron una estructura de datos para evaluar polinomios sobre un campo finito de tamaño${\displaystyle F_{q}}$a tiempo${\displaystyle (\log n)^{O(1)}(\log _{2}q)^{1+o(1)}}$por evaluación después de un preprocesamiento inicial. Larsen ^{[ 8 ]} demostró que esto era esencialmente óptimo.

La idea es transformar${\displaystyle P(x)}$de grado${\displaystyle n}$en un polinomio multivariado${\displaystyle f(x_{1},x_{2},\dots ,x_{m})}$, de tal manera que${\displaystyle P(x)=f(x,x^{d},x^{d^{2}},\dots ,x^{d^{m}})}$y los grados individuales de${\displaystyle f}$es como máximo${\displaystyle d}$. Dado que esto ha terminado${\displaystyle {\bmod {q}}}$, el mayor valor${\displaystyle f}$puede tomar (más de${\displaystyle \mathbb {Z} }$) es${\displaystyle M=d^{m}(q-1)^{dm}}$. Utilizando el teorema chino del resto , basta con evaluar${\displaystyle f}$módulo diferentes primos${\displaystyle p_{1},\dots ,p_{\ell }}$con un producto al menos${\displaystyle M}$Cada número primo puede considerarse aproximadamente igual a...${\displaystyle \log M=O(dm\log q)}$y el número de primos necesarios,${\displaystyle \ell }$es aproximadamente lo mismo. Al realizar este proceso recursivamente, podemos obtener primos tan pequeños como${\displaystyle \log \log q}$Eso significa que podemos calcular y almacenar${\displaystyle f}$en todos los valores posibles en${\displaystyle T=(\log \log q)^{m}}$tiempo y espacio. Si tomamos${\displaystyle d=\log q}$, obtenemos${\displaystyle m={\tfrac {\log n}{\log \log q}}}$, por lo que el requisito de tiempo/espacio es${\displaystyle n^{\frac {\log \log q}{\log \log \log q}}.}$

Kedlaya y Umans muestran además cómo combinar este preprocesamiento con una evaluación multipunto rápida mediante la transformada rápida de Fourier. Esto permite obtener algoritmos óptimos para muchos problemas algebraicos importantes, como la composición modular polinomial .

Un tipo de polinomio particularmente interesante son las potencias como${\displaystyle x^{n}}$. Dichos polinomios siempre se pueden calcular en${\displaystyle O(\log n)}$operaciones. Supongamos, por ejemplo, que necesitamos calcular${\displaystyle x^{16}}$; podríamos simplemente comenzar con${\displaystyle x}$y multiplicar por${\displaystyle x}$Llegar${\displaystyle x^{2}}$. Luego podemos multiplicarlo por sí mismo para obtener${\displaystyle x^{4}}$y así sucesivamente para obtener${\displaystyle x^{8}}$y${\displaystyle x^{16}}$en tan solo cuatro multiplicaciones. Otras potencias como${\displaystyle x^{5}}$De manera similar, se puede calcular de manera eficiente calculando primero${\displaystyle x^{4}}$por 2 multiplicaciones y luego multiplicando por${\displaystyle x}$.

La forma más eficiente de calcular una potencia determinada${\displaystyle x^{n}}$se proporciona mediante la exponenciación en cadena de adición . Sin embargo, esto requiere diseñar un algoritmo específico para cada exponente, y el cálculo necesario para diseñar estos algoritmos es difícil ( NP-completo ^{[ 9 ]} ), por lo que la exponenciación por cuadrado se prefiere generalmente para cálculos efectivos.

A menudo, los polinomios aparecen en una forma diferente a la bien conocida.${\displaystyle a_{n}x^{n}+\dots +a_{1}x+a_{0}}$Para polinomios en forma de Chebyshev podemos usar el algoritmo de Clenshaw . Para polinomios en forma de Bézier podemos usar el algoritmo de De Casteljau , y para B-splines existe el algoritmo de De Boor .

El hecho de que algunos polinomios se puedan calcular significativamente más rápido que los "polinomios generales" plantea la pregunta: ¿Podemos dar un ejemplo de un polinomio simple que no se pueda calcular en un tiempo mucho menor que su grado? Volker Strassen ha demostrado ^{[ 10 ]} que el polinomio

${\displaystyle P(x)=\sum _{k=0}^{n}2^{2^{kn^{3}}}x^{k}}$

no se puede evaluar con menos de${\displaystyle {\tfrac {1}{2}}n-2}$multiplicaciones y${\displaystyle n-4}$adiciones. Al menos este límite se cumple si solo se permiten operaciones de esos tipos, dando lugar a una llamada "cadena polinómica de longitud${\displaystyle <n^{2}/\log n}$".

El polinomio dado por Strassen tiene coeficientes muy grandes, pero mediante métodos probabilísticos se puede demostrar que deben existir incluso polinomios con coeficientes solo 0 y 1 tales que la evaluación requiere al menos${\displaystyle \Omega (n/\log n)}$multiplicaciones. ^{[ 11 ]}

Para otros polinomios simples, la complejidad es desconocida. El polinomio${\displaystyle (x+1)(x+2)\cdots (x+n)}$Se conjetura que no es computable en el tiempo${\displaystyle (\log n)^{c}}$para cualquier${\displaystyle c}$Esto se ve respaldado por el hecho de que, si se puede calcular rápidamente, la factorización de enteros se puede calcular en tiempo polinomial, rompiendo el criptosistema RSA . ^{[ 12 ]}