Horner polynomial evaluation

ddanbe 0 916 Views

Short snippet in C# to do this classic trick, I could not find one on the web. Little, (even none!) error checking is done here.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Horner
{
    class Program
    {
        //here it all happens
        static double Horner(double[] coeffients, int degree, double value)
        {
            double result = coeffients[degree];
            for (int i = degree - 1; i >= 0; i--)
            {
                result = result * value + coeffients[i];
            }
            return result;
        }


        //Main function to exercise the above
        static void Main(string[] args)
        {
            //coefficient array
            double[] c = {0,0,0,0,0,0,0,0,0,0,0};   //degree 10 maximum
            //highest degree
            int d;
            //value to be evaluated
            double v;
            Console.WriteLine("HORNER polynomial evaluator.");
            Console.WriteLine();
            Console.Write("Enter degree of polynomial: ");
            d = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine("Fill in coefficients from low to high degree.");
            Console.WriteLine("Coefficients, a[0], a[1], ..., a[" + d.ToString() + "]");
            for (int i = 0; i <= d; i++)
            {
                Console.Write("Coefficient a[" + i.ToString() + "] = ");
                c[i] = Convert.ToDouble(Console.ReadLine());
            }
            Console.Write("Enter the value to be evaluated: ");
            v = Convert.ToDouble(Console.ReadLine());

            double r = Horner(c, d, v);
            Console.WriteLine("------------------------------------------------");
            Console.WriteLine("The calculated value for this polynomial is : {0}",r);

        }
    }
}

Dani AI

Generated

Nice, compact example from . demonstrates using Horner for synthetic division to test integer roots (try divisors of the constant term), and points out a concise LINQ take. The following adds practical hardening, a numerical caution, and a short helper to compute the derivative in the same pass — all while keeping Horner's O(n) efficiency.

Input and storage hardening: allocate the coefficient array to match the entered degree, and use TryParse to avoid exceptions. Trim any high-order zeros to detect the true degree before evaluating. Example parsing pattern (no Horner code repeated here):

// allocate after reading degree
int d;
while (!int.TryParse(Console.ReadLine(), out d) || d < 0)
    Console.Write("Enter non-negative integer degree: ");
double[] coeffs = new double[d + 1];
for (int i = 0; i <= d; i++) {
    Console.Write($"a[{i}] = ");
    while (!double.TryParse(Console.ReadLine(), out coeffs[i]))
        Console.Write("Invalid number, try again: ");
}

Numerical cautions and root-testing: Horner minimizes operations and usually improves numerical behavior versus naive power evaluation, but rounding and overflow remain for very large degrees, wildly scaled coefficients, or huge evaluation points. For financial/decimal-exact needs consider decimal or an arbitrary-precision library; for integer root searches like does, use long or BigInteger when coefficients or intermediate values might overflow.

Evaluate polynomial and its derivative together (one pass): this variant returns P(x) and P'(x) without a second Horner pass.

double EvaluateWithDerivative(double[] a, double x, out double derivative) {
    int n = a.Length - 1;
    double y = a[n];
    double yp = 0.0;
    for (int i = n - 1; i >= 0; i--) {
        yp = yp * x + y;
        y  = y  * x + a[i];
    }
    derivative = yp;
    return y;
}

These small changes keep the implementation simple and robust while respecting the algorithmic strengths mentioned by the original posters.

Member Avatar for Jaroslav_1
Jaroslav_1 15 Newbie Poster

I found here "good" source code in c# for Horner scheme:

private IEnumerable<int> getDivisors(int n)
{
    if (n == 0)
        return (IEnumerable<int>)new int[] { 0 };
    else
        return Enumerable.Range(-Math.Abs(n), 2 * Math.Abs(n) + 1)
            .Where(a => a != 0)
            .Where(a => (n % a) == 0);
}
private bool findRootWithHornerScheme(int[] coefficientsA, int x, out int[] coefficientsB)
{
    var lenght = coefficientsA.Length;
    var tmpB = new int[lenght];
    coefficientsB = new int[lenght - 1];
    tmpB[0] = coefficientsA[0];
    for (int i = 1; i < lenght; i++)
    {
        tmpB[i] = tmpB[i - 1] * x + coefficientsA[i];
    }
    //ak je posledny koefiecient B == 0 ,tak zadane x je korenom polynomu
    if (tmpB[lenght - 1] == 0)
    {
        Array.Copy(tmpB, coefficientsB, lenght - 1);
        return true;//bol najdeny koren
    }
    //nebol najdeny koren a metoda vrati false
    return false;
}
commented: Nice! +15
Member Avatar for Gribouillis
Gribouillis 1,391 Programming Explorer

There is also an implementation at Rosetta code. It is very short, but I haven't used C# for a long time, so I don't know if it is good.

ddanbe commented: Thanks for the tip. :) +15
Member Avatar for ddanbe
ddanbe 2,724 Professional Procrastinator

My version was before LINQ was introduced in C#. The Rosetta code version uses LINQ in an excellent way.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Edit Preview