Hispanopedia Wiki
Articulo de referencia

Algoritmo de Knuth-Eve

En informática , el algoritmo de Knuth-Eve es un algoritmo para la evaluación de polinomios . Preprocesa los coeficientes del polinomio para reducir el número de multiplicacione...

Hispanopedia WikiContenido en espanolLectura gratuita

En informática , el algoritmo de Knuth-Eve es un algoritmo para la evaluación de polinomios . Preprocesa los coeficientes del polinomio para reducir el número de multiplicaciones necesarias en tiempo de ejecución .

Las ideas empleadas en el algoritmo fueron propuestas originalmente por Donald Knuth en 1962. Su procedimiento aprovecha de manera oportunista la estructura del polinomio que se está evaluando. [ 1 ] En 1964, James Eve determinó para qué polinomios existe esta estructura y proporcionó un método sencillo de "preacondicionamiento" de polinomios (explicado más adelante) para dotarlos de dicha estructura. [ 2 ] [ nota 1 ]

Algoritmo

Preliminares

Consideremos un polinomio arbitrariopag∈R[incógnita]{\displaystyle p\in \mathbb {R} [x]}de gradonorte{\displaystyle n}. Supongamos quenorte≥3{\displaystyle n\geq 3}. Definirmetro{\displaystyle m}tal que: sinorte{\displaystyle n}entonces es extrañonorte=2metro+1{\displaystyle n=2m+1}y sinorte{\displaystyle n}es incluso entoncesnorte=2metro+2{\displaystyle n=2m+2}. [ 2 ]

Salvo que se indique lo contrario, todas las variables de este artículo representan números reales o polinomios univariados con coeficientes reales. [ 1 ] [ 2 ] Todas las operaciones de este artículo se realizan sobreR{\displaystyle \mathbb {R} }. [ 2 ]

Nuevamente, el objetivo es crear un algoritmo que devuelvapag(incógnita){\displaystyle p(x)}dado cualquierincógnita{\displaystyle x}. El algoritmo puede depender del polinomiopag{\displaystyle p}en sí misma, ya que sus coeficientes se conocen de antemano. [ 1 ]

Descripción general

Idea clave

Usando la división larga de polinomios , podemos escribir

pag(incógnita)=q(incógnita)⋅(incógnita2−α)+(βincógnita+γ),{\displaystyle p(x)=q(x)\cdot (x^{2}-\alpha )+(\beta x+\gamma ),}

dóndeincógnita2−α{\displaystyle x^{2}-\alpha }es el divisor. Elegir un valor paraα{\displaystyle \alpha }corrige ambos cocientesq{\displaystyle q}y los coeficientes en el restoβ{\displaystyle \beta }yγ{\displaystyle \gamma }La idea clave es elegir inteligentementeα{\displaystyle \alpha }de tal manera queβ=0{\displaystyle \beta =0}, de modo que

pag(incógnita)=q(incógnita)⋅(incógnita2−α)+γ.{\displaystyle p(x)=q(x)\cdot (x^{2}-\alpha )+\gamma .}

[ 4 ] De esta manera, no se necesitan operaciones para calcular el polinomio restante, ya que es simplemente una constante. Aplicamos este procedimientorecursivamenteaq{\displaystyle q}, expresando

pag(incógnita)=((q(incógnita)⋅(incógnita2−αmetro)+γmetro)⋯)⋅(incógnita2−α1)+γ1.{\displaystyle p(x)=\left(\left(q(x)\cdot (x^{2}-\alpha _{m})+\gamma _{m}\right)\cdots \right)\cdot (x^{2}-\alpha _{1})+\gamma _{1}.}

Despuésmetro{\displaystyle m}llamadas recursivas, el cocienteq{\displaystyle q}es un polinomio lineal o cuadrático . En este caso base, el polinomio se puede evaluar con (por ejemplo) el método de Horner . [ 1 ] [ 4 ] [ 5 ]

"Preacondicionamiento"

Para arbitrariopag{\displaystyle p}, puede que no sea posible forzarβ=0{\displaystyle \beta =0}en cada paso de la recursión. [ 1 ] Consideremos los polinomiospagmi{\displaystyle p^{e}}ypago{\displaystyle p^{o}}con coeficientes tomados de los términos pares e impares depag{\displaystyle p}respectivamente, de modo que

pag(incógnita)=pagmi(incógnita2)+incógnita⋅pago(incógnita2).{\displaystyle p(x)=p^{e}(x^{2})+x\cdot p^{o}(x^{2}).}

Si cada raíz depago{\displaystyle p^{o}}es real, entonces es posible escribirpag{\displaystyle p}en el formato dado anteriormente. Cadaαi{\displaystyle \alpha _{i}}es una raíz diferente depago{\displaystyle p^{o}}, contando las raíces múltiples como distintas. [ 4 ] Además, si al menosnorte−1{\displaystyle n-1}raíces depag{\displaystyle p}si se encuentran en la mitad del plano complejo , entonces cada raíz depago{\displaystyle p^{o}}es real. [ 2 ]

En última instancia, puede ser necesario "preacondicionar".pag{\displaystyle p}al cambiarlo , al configurarlopag(incógnita)←pag(incógnita+t){\displaystyle p(x)\gets p(x+t)}para algunost{\displaystyle t}— para dotarlo de la estructura de que la mayoría de sus raíces se encuentran en una mitad del plano complejo. En tiempo de ejecución, este cambio debe "deshacerse" estableciendo primeroincógnita←incógnita−t{\displaystyle x\gets xt}. [ 2 ]

Paso de preprocesamiento

El siguiente algoritmo se ejecuta una vez para un polinomio dado.pag{\displaystyle p}. [ 1 ] [ 4 ] En este punto, los valores deincógnita{\displaystyle x}esopag{\displaystyle p}se evaluarán en función de que no se conocen. [ 1 ]

  • Dejarr1,⋯,rnorte∈do{\displaystyle r_{1},\cdots ,r_{n}\in \mathbb {C} }ser las raíces complejas depag{\displaystyle p}ordenados en orden descendente por parte real
  • Elige cualquierat≥Re(r2){\displaystyle t\geq {\text{Re}}(r_{2})}
  • Colocarpag←pag(incógnita+t){\displaystyle p\gets p(x+t)}
  • Dejarpagmi{\displaystyle p^{e}}ypago{\displaystyle p^{o}}sean los polinomios tales quepag(incógnita)=pagmi(incógnita2)+incógnita⋅pago(incógnita2){\displaystyle p(x)=p^{e}(x^{2})+x\cdot p^{o}(x^{2})}
  • Dejarα1,⋯αmetro∈R{\displaystyle \alpha _{1},\cdots \alpha _{m}\in \mathbb {R} }ser las raíces depago{\displaystyle p^{o}}Todas sus raíces serán reales.
  • Inicializarq←pag{\displaystyle q\gets p}
  • Parai←1,⋯,metro{\displaystyle i\gets 1,\cdots ,m}:
    • Dividirq{\displaystyle q}porincógnita2−αi{\displaystyle x^{2}-\alpha _{i}}para obtener cocienteq′∈R[incógnita]{\displaystyle q^{\prime }\in \mathbb {R} [x]}y el restoγi∈R{\displaystyle \gamma _{i}\in \mathbb {R} }. El resto será un polinomio constante, es decir, un número.
    • Colocarq←q′{\displaystyle q\gets q^{\prime }}
  • Salida: Los valores derivadost{\displaystyle t},α1,⋯,αmetro{\displaystyle \alpha _{1},\cdots ,\alpha _{m}}, yγ1,⋯,γmetro{\displaystyle \gamma _{1},\cdots ,\gamma _{m}}; así como el polinomio del caso baseq{\displaystyle q}

Mejor elección de t

Mientras que cualquiert≥Re(r2){\displaystyle t\geq {\text{Re}}(r_{2})}puede funcionar, es posible eliminar una adición durante la evaluación sit{\displaystyle t}también se elige de tal manera que dos raíces depag(incógnita+t){\displaystyle p(x+t)}son simétricas respecto al origen. En ese caso,α1{\displaystyle \alpha _{1}}se puede elegir de tal manera que el polinomio desplazado tenga un factor deincógnita2−α1{\displaystyle x^{2}-\alpha _{1}}, entoncesγ1=0{\displaystyle \gamma _{1}=0}Siempre es posible encontrar tal cosa.t{\displaystyle t}. [ 2 ]

Un posible algoritmo para elegirt{\displaystyle t}es:

  • Sir1∈R{\displaystyle r_{1}\in \mathbb {R} }:
    • Sir2∈R{\displaystyle r_{2}\in \mathbb {R} }:t=12(r1+r2){\textstyle t={\tfrac {1}{2}}(r_{1}+r_{2})}
    • Demás:t=Re(r2){\displaystyle t={\text{Re}}(r_{2})}
  • Demás:t=Re(r1){\displaystyle t={\text{Re}}(r_{1})}

Paso de evaluación

El siguiente algoritmo evalúapag{\displaystyle p}en algún punto, ahora conocidoincógnita{\displaystyle x}. [ 1 ] [ 2 ] [ 4 ] [ 5 ]

  • Colocarincógnita←incógnita−t{\displaystyle x\gets x-t}
  • Dejars=incógnita2{\displaystyle s=x^{2}}Calcula esto una sola vez para que pueda reutilizarse.
  • Calculary←q(incógnita){\displaystyle y\gets q(x)}utilizando el método de Horner
  • Parai←metro,⋯,2,1{\displaystyle i\gets m,\cdots ,2,1}:
    • Dejary←y⋅(s−αi)+γi{\displaystyle y\gets y\cdot (s-\alpha _{i})+\gamma _{i}}
  • Producción:y{\displaystyle y}

Arrogantet{\displaystyle t}se elige de forma óptima,γ1=0{\displaystyle \gamma _{1}=0}. Por lo tanto, la iteración final del bucle puede ejecutarse en su lugar.

y←y⋅(s−αi),{\displaystyle y\gets y\cdot (s-\alpha _{i}),}

ahorrar una adición. [ 2 ]

Análisis

En total, evaluación utilizando el algoritmo de Knuth-Eve para un polinomio de gradonorte{\displaystyle n}requierenorte{\displaystyle n}adiciones y⌊norte/2⌋+2{\displaystyle \lfloor n/2\rfloor +2}multiplicaciones, suponiendot{\displaystyle t}se elige de forma óptima. [ 2 ]

No existe ningún algoritmo para evaluar un polinomio dado de gradonorte{\displaystyle n}puede utilizar menos denorte{\displaystyle n}adiciones o menos de⌈norte/2⌉{\displaystyle \lceil n/2\rceil }multiplicaciones durante la evaluación. Este resultado supone que solo se permiten sumas y multiplicaciones durante el preprocesamiento y la evaluación. [ 6 ]

El algoritmo de Knuth-Eve no está bien condicionado . [ 7 ]

Notas a pie de página

  1. ↑ Artículo publicado bajo el nombre de J. Eve, que está asociado con el nombre de James Eve por la Biblioteca Digital de la ACM. [ 3 ]

Referencias

  1. 1 2 3 4 5 6 7 8 Knuth, Donald (diciembre de 1962). "Evaluación de polinomios por computadora" . Communications of the ACM . 5 (12): 595– 599. doi : 10.1145/355580.369074 . Recuperado el 25 de julio de 2025 .
  2. 1 2 3 4 5 6 7 8 9 10 Eve, James (diciembre de 1964). "La evaluación de polinomios" . Numerische Mathematik . 6 (1): 17– 21. doi : 10.1007/BF01386049 . Recuperado el 25 de julio de 2025 .
  3. ↑ "James Eve (Universidad de Newcastle)" . Serie DO del autor . Biblioteca digital de ACM. doi : 10.1145/contrib-81100250587/abs (inactivo el 31 de julio de 2025) . Recuperado el 30 de julio de 2025 .{{cite web}}: CS1 maint: DOI inactivo desde julio de 2025 ( enlace )
  4. 1 2 3 4 5 Overill, Richard (12 de junio de 1997). "Evaluación paralela de datos de polinomios univariados mediante el algoritmo de Knuth-Eve" . Computación paralela . 23 (13): 2115–2127 . doi : 10.1016/S0167-8191(97)00096-3 . Recuperado el 25 de julio de 2025 .
  5. 1 2 Muller, Jean-Michel (17 de noviembre de 2016). Funciones elementales: algoritmos e implementación . Boston, MA: Birkhäuser Boston. págs. 82–84 . doi : 10.1007/978-1-4899-7983-4_5 . ISBN  978-1-4899-7983-4Consultado el 25 de julio de 2025 .
  6. ↑ Erickson, Jeff (10 de marzo de 2003). "Evaluación de polinomios" (PDF) . CS 497: Modelos concretos de computación . Universidad de Illinois Urbana-Champaign . Consultado el 25 de julio de 2025 .
  7. ↑ Mesztenyi, Charles (enero de 1967). "Evaluación estable de polinomios" . Journal of Research of the National Bureau of Standards, Section B. 71B ( 1): 11– 17. doi : 10.6028/jres.071B.003 . Consultado el 25 de julio de 2025 .