Implementing Horner Algorithm for Polynomial Evaluation in C#

Horner Algorith is considered one of the best(if not the best) methods for evaluating polynomials in monomial form. This algorithm is very efficient because it allows for quickly and very precise evaluations, saving lots of processor cycles.

 Best way to understand this method is by checking out one numerical example, the example consists of making lots of factorization of one function, until you can't anymore, then solve the factorized function for a given x value :

f(x) = 4x³ + 3x² + 2x + 1

f(x) = (4x² + 3x + 2)x + 1

f(x) = ((4x + 3)x + 2)x + 1

f(x) = (((4)x + 3)x + 2)x + 1

Now, let's evaluate function for x = 3:

f(x) =(((4)(3) + 3)(3) + 2)(3) + 1

f(x) = ((12 + 3)(3) + 2)(3) + 1

f(x) = ((15)(3) + 2)(3) + 1

f(x) = (45 + 2)(3) + 1

f(x) = (47)(3) + 1

f(x) = 141 + 1

f(x) = 142

Our coefficients are N₁ = 4, N₂ = 3, N₃ = 2, N₄ = 1. It was important to put all mathematical procedure in this example, because we must observe that if we factorize our function and evaluate with the resulting function, we'll do it by first multiplying N₁ coefficient by x, then summing this product with N₂ coefficient , multiply this sum by x again, sum this product with N₃ coefficient, multiply this sum by x, and finally sum N₄ coefficient and we have our result. This procedure is repetitive, it means we can easily turn it into one fully functional algorithm.

For efficient programming in C# it's a good idea to store all coefficients in one array. For example, for the given example our array would be something like: [ 4, 3, 2, 1]. Let's check out C# code:

//Made by Henry Serrano 28/7/2011

//You can use/modify code in any way you like

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace HornerAlgorithm

{

    class Program

    {

        static void Main(string[] args)

        {

            //coefficients of our polynomial

            //f(x) = 4x^3 + 3x^2 + 2x + 1

            double[] coefficients = new double[] { 4, 3, 2, 1};

            Console.WriteLine(horner(coefficients, 3));

            Console.ReadLine();

        }

        static double horner(double[] coefficients, double x)

        {

            double result = 0;

            //horner algorithm

            //------------------

            result = coefficients[0] * x;

            for (int i = 1; i < (coefficients.Length - 1); i++)

            {

                result += coefficients[i];

                result *= x;

            }

            result += coefficients[coefficients.Length - 1];

            //------------------

            return result;

        }

    }

}

Function "horner" is the implementation of Horner Algorithm, only requires one coefficient array and x value. There is no limit for the polynomial grade with the horner algorithm, the only trouble would be getting its coefficients. I'll attach the full project for download:

Horner Algorithm C# download