Método de Horner – Algoritmos antiguos

En este artículo de discutirá el método de Horner para la resolución de polinomios y su aplicación en varios lenguajes.

El método de Horner, también llamado la regla de Horner es un algoritmo que permite calcular el resultado de un polinomio para un determinado valor de x.

El algoritmo tiene ese nombre por el matemático británico William George Horner aunque él no fue el primer en encontrar este método siendo conocido por un gran número de matemáticos de la antigüedad. Su primera aparición es en el libro matemático «Los nueve capítulos de el arte matemático», un libro realizado por varias generaciones de estudiosos en China entre los siglos I y II AC.

Otros conocedores de este algoritmo fueron el matemático chino del siglo XI Jia Xian, el matemático persa Sharaf al-Din al-Tusi en el siglo XII  y el matemático chino Zhu Shijie en el siglo XIV .

La eficiencia del método de Horner

Aunque la solución de un polinomio para un valor específico de x es una tarea sencilla el algoritmo reduce la cantidad de operaciones necesarias para llegar al resultado lo que la convierte en una técnica más eficiente y más deseable a la hora de programarla.

Llamando a el grado del polinomio g una resolución por sustituciones requiere hasta (g²+g)/2 multiplicaciones y g sumas mientras que el algoritmo de Horner solo requerirá g sumas y g multiplicaciones.

Veremos la diferencia para el siguiente polinomio de grado 4 y valor de x:

Resolución por sustitución

Esta resolución es la manera clásica donde se sustituye la x por el valor deseado y luego se realizan las operaciones necesarias.

Método de Horner

Colocamos los coeficientes del polinomio en una tabla junto con el valor de x que quiere evaluarse.

Bajamos el primer coeficiente y lo multiplicamos por el valor de x colocando el resultado debajo del siguiente coeficiente en la tabla.

Sumamos los dos valores obteniendo un nuevo resultado parcial.

Repetimos la operación para cada coeficiente.

Al llegar al último coeficiente obtenemos el resultado final

Podemos ver en este ejemplo como se ha reducido la cantidad de multiplicaciones necesarias ahorrando al sistema 6 operaciones extras.

Método de Horner – Algoritmo

• Pseudocódigo con Pseint
• Algoritmo para PHP
• Algorimto para C
• Algoritmo para Python

Pseudocódigo para PSeint

Proceso Horner
	//Valor e x
	valorX=8;
	//Coeficientes del polinomio
	dimensionArreglo=5;
	Dimension coeficientes[dimensionArreglo];
	coeficientes[1]=4;
	coeficientes[2]=7;
	coeficientes[3]=3;
	coeficientes[4]=6;
	coeficientes[5]=2;
	
	resultado=0;
	//Recorrer los coeficientes
	Para i=1 Hasta dimensionArreglo Con Paso 1 Hacer
		//Multiplicar al valor parcial el valor de x más el coeficiente
		resultado= resultado * valorX + coeficientes[i];
	FinPara
	Escribir "Resultado: " resultado;
	
FinProceso

Código para C

#include<stdio.h>

int main(int argc, char** argv){

	//Valor de x
	float valorX=8;
	//Coeficientes del polinomio
	float coeficientes[]={4,7,3,6,2};
	float resultado=0;
	int i;

	//Recorrer los coeficientes
	for(i=0;i<(sizeof(coeficientes)/sizeof(float));i++){
	  //Multiplicar al valor parcial el valor de x más el coeficiente
	  resultado= resultado * valorX + coeficientes[i];
	}

	printf("Resultado %f\n",resultado);
	return 0;
}

Código para PHP

<?php

//Valor de x
$valorX=8;
//Coeficientes del polinomio
$coeficientes=array(4,7,3,6,2);
$resultado=0;
//Recorrer los coeficientes
for($i=0;$i<count($coeficientes);$i++)
{
	//Multiplicar al valor parcial el valor de x más el coeficiente
	$resultado= $resultado * $valorX + $coeficientes[$i];
}

echo "Resultado: ".$resultado;

Código para Python

#Valor de x
valorX=8;
#Coeficientes del polinomio
coeficientes=[4,7,3,6,2];
resultado=0;
#Recorrer los coeficientes
for i in range(0,len(coeficientes)):
	#Multiplicar al valor parcial el valor de x más el coeficiente
	resultado= resultado * valorX + coeficientes[i]
print("Resultado:"+str(resultado))

Espero que les sirva!