En análisis numérico , el esquema de Estrin (en honor a Gerald Estrin ), también conocido como método de Estrin , es un algoritmo para la evaluación numérica de polinomios .
El método de Horner para la evaluación de polinomios es uno de los algoritmos más utilizados para este propósito y, a diferencia del esquema de Estrin, es óptimo en el sentido de que minimiza la cantidad de multiplicaciones y sumas necesarias para evaluar un polinomio arbitrario. En un procesador moderno, las instrucciones que no dependen de los resultados de las demás pueden ejecutarse en paralelo. El método de Horner contiene una serie de multiplicaciones y sumas que dependen cada una de la instrucción anterior y, por lo tanto, no pueden ejecutarse en paralelo. El esquema de Estrin es un método que intenta superar esta serialización y, al mismo tiempo, se mantiene razonablemente cerca de ser óptimo.
El esquema de Estrin opera recursivamente , convirtiendo un polinomio de grado n en x (para n ≥2) en un polinomio de grado ⌊ n /2 ⌋ en x 2 usando ⌈ n /2⌉ operaciones independientes (más una para calcular x 2 ).
Dado un polinomio arbitrario P ( x ) = C 0 + C 1 x + C 2 x 2 + C 3 x 3 + ⋯ + C n x n , se pueden agrupar términos adyacentes en subexpresiones de la forma ( A + Bx ) y reescribirlo como un polinomio en x 2 : P ( x ) = ( C 0 + C 1 x ) + ( C 2 + C 3 x ) x 2 + ( C 4 + C 5 x ) x 4 + ⋯ = Q ( x 2 ).
Cada una de estas subexpresiones, y x 2 , se pueden calcular en paralelo. También se pueden evaluar utilizando una instrucción nativa de multiplicación-acumulación en algunas arquitecturas, una ventaja que comparte con el método de Horner.
Esta agrupación puede luego repetirse para obtener un polinomio en x 4 : P ( x ) = Q ( x 2 ) = (( C 0 + C 1 x ) + ( C 2 + C 3 x ) x 2 ) + (( C 4 + C 5 x ) + ( C 6 + C 7 x ) x 2 ) x 4 + ⋯ = R ( x 4 ).
Repitiendo este ⌊ log 2 n ⌋ +1 veces, se llega al esquema de Estrin para la evaluación paralela de un polinomio:
Esto realiza un total de n operaciones de multiplicación-acumulación (lo mismo que el método de Horner) en la línea 1, y ⌊ log 2 n ⌋ cuadrados adicionales en la línea 3. A cambio de esos cuadrados adicionales, todas las operaciones en cada nivel del esquema son independientes y pueden calcularse en paralelo; la ruta de dependencia más larga tiene una longitud de ⌊ log 2 n ⌋ +1 operaciones.
Tome P n ( x ) como el polinomio de orden n de la forma: P n ( x ) = C 0 + C 1 x + C 2 x 2 + C 3 x 3 + ⋯ + C n x n
Escribiendo con el esquema de Estrin tenemos:
Con todo detalle, consideremos la evaluación de P 15 ( x ):