Horner's Rule

Horner’s rule is an efficient algorithm to evaluate polynomials. For a polynomial:

P(x) = anx^n + an-1x^(n-1) + ….. + a1*x + a0

Horner’s rule states that:

P(x) = (((…(an*x + an-1)*x + an-2)*x…) + a1)*x + a0

This formulation allows polynomial evaluation in O(n) time rather than O(n^2) by naive expansion.

Horner’s rule leverages polynomial structure for efficiency. It is useful for speeding up computations.

Solution

Here is how Horner’s rule can be implemented:

Java

1
2
3
4
5
6
7
double horner(double[] coefficients, double x) {
  double result = coefficients[0];
  for(int i=1; i < coefficients.length; i++) {
    result = result*x + coefficients[i];
  }
  return result;
}

C++

1
2
3
4
5
6
7
double horner(vector<double> coefficients, double x) {
  double result = coefficients[0];
  for(int i=1; i < coefficients.size(); i++) {
    result = result*x + coefficients[i];
  }
  return result;
}

Python

1
2
3
4
5
6
7
def horner(coefficients, x):

  result = coefficients[0]
  for i in range(1, len(coefficients)):
    result = result*x + coefficients[i]

  return result

Horner’s rule leverages polynomial structure for efficient evaluation.

Description: Horner’s Rule

Horner’s Rule is a mathematical algorithm used for efficient evaluation of polynomial equations. Given a polynomial equation ( P(x) = a_0 + a_1 \cdot x + a_2 \cdot x^2 + \cdots + a_n \cdot x^n ), Horner’s Rule allows us to evaluate ( P(x) ) with fewer multiplications and additions compared to the naive approach. The method restructures the polynomial as a nested expression: ( P(x) = a_0 + x \cdot (a_1 + x \cdot (a_2 + \cdots x \cdot (a_{n-1} + x \cdot a_n) \cdots )) ).

Solution:

Below are implementations of Horner’s Rule to evaluate a polynomial for a given value of ( x ) in Java, C++, and Python.

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
public class Horner {
    public static double evaluate(double[] coefficients, double x) {
        double result = 0;
        for (int i = coefficients.length - 1; i >= 0; i--) {
            result = result * x + coefficients[i];
        }
        return result;
    }

    public static void main(String[] args) {
        double[] coefficients = {1, 2, 3, 4}; // 1 + 2x + 3x^2 + 4x^3
        double x = 2;
        double result = evaluate(coefficients, x);
        System.out.println("Result: " + result); // Should output 49
    }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <vector>

double evaluate(std::vector<double> coefficients, double x) {
    double result = 0;
    for (int i = coefficients.size() - 1; i >= 0; i--) {
        result = result * x + coefficients[i];
    }
    return result;
}

int main() {
    std::vector<double> coefficients = {1, 2, 3, 4}; // 1 + 2x + 3x^2 + 4x^3
    double x = 2;
    double result = evaluate(coefficients, x);
    std::cout << "Result: " << result << std::endl; // Should output 49
    return 0;
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def evaluate(coefficients, x):
    result = 0
    for coef in reversed(coefficients):
        result = result * x + coef
    return result

coefficients = [1, 2, 3, 4]  # 1 + 2x + 3x^2 + 4x^3
x = 2
result = evaluate(coefficients, x)
print("Result:", result)  # Should output 49

Key Takeaways

Horner’s Rule allows efficient evaluation of polynomials.
The algorithm reduces the number of operations involved in computing ( P(x) ).
Java, C++, and Python offer simple and clear ways to implement Horner’s Rule.
The rule is particularly useful in computer graphics, data fitting algorithms, and many other areas where polynomials are used.