How to Find Value of Polynomial Using Horner's Rule in C++

1. Find the Value of Polynomial Using Horner’s Rule in C++ by Iterating the Loop Backward
2. Find the Value of Polynomial Using Horner’s Rule in C++ by Iterating the Loop Forward
3. Use Recursion to Find the Value of Polynomial Using Horner’s Rule in C++
4. Conclusion

Horner’s rule is an efficient algorithm for computing the value of a polynomial.

Consider the polynomial p(x) = 6x^3 - 2x^2 + 7x + 5 at x = 4. To compute it using Horner’s rule in C++, the first coefficient, 6, is multiplied by the value at x, which is 4, and the product of the two being 24, gets added to the next coefficient -2.

The resultant is multiplied by 4 and added to the next coefficient.

This process is repeated for the number of coefficients in the equation. The end product left is the value of the polynomial.

This article explains how to find the value of a polynomial using Horner’s rule in C++ by converting the above rules into computer code.

Let’s consider a polynomial:

If x = 4, the value of the polynomial is 385.

Find the Value of Polynomial Using Horner’s Rule in C++ by Iterating the Loop Backward

Let’s look at the program that finds the value of a polynomial using Horner’s rule in C++ by backward looping.

1. The first line of code imports the library package iostream; in the second line, the namespace is defined as std.

2. A method int Horner() is created with three parameters - a pointer array a that will pass the list of coefficients, integer variable n which stores the degree of the polynomial, and another integer variable x which stores the polynomial’s value at x.

   int Horner(int* a, int n, int x)
   

3. This explains how to add the product of polynomials to each other. An integer variable result is created, initialized with the last element of the array a[n].

   int result = a[n];
   

   Note: Do not mistake it as the size of the array; it initializes the variable result with the element in array a at the nth position.

4. A for loop is created, reversing the loop from the last element of array a to the 0th index. The value of the result variable gets updated for each loop iteration.

   for (int i = n - 1; i >= 0; --i) 
   

   In the first iteration, the value of a[n] is multiplied with x and then added to the previous element in the array - a[n-1]. For an array - {2,3,4}, the loop will take the last element a[n], which is 4, multiply it with x, and then add to the n-1 element of the array, which is 3.

   For this reason, the coefficients need to be reversed while initializing in the main function. The value of result is returned at the end of the method.

5. Inside the main function, an array is created to pass it to the first parameter of method Horner. Note that the value of coefficients inside the array is reversed because the loop iterates backward.

6. An integer variable sol is created to store the result returned from the method named Horner.

   In the first parameter, the array that is being created is passed. The second parameter passes the degree of polynomials in the equation, 3, and the third parameter value at x is passed.

   int sol = Horner(arr, 3, 4);
   

Code:

#include <iostream>
using namespace std;
int Horner(int* a, int n, int x) {
  int result = a[n];
  for (int i = n - 1; i >= 0; --i) result = result * x + a[i];
  return result;
}

int main() {
  int arr[4] = {5, 7, -2, 6};
  int sol = Horner(arr, 3, 4);
  cout << sol;
}

Output (Backward looping Horner’s rule in C++):

385

Find the Value of Polynomial Using Horner’s Rule in C++ by Iterating the Loop Forward

If we need to run the loop forward, unlike the last example, we can dereference the pointer of the array to get its first element and run the loop forward instead of reversing it. It is another way to use loops to implement Horner’s rule in C++.

Let’s understand what the code does:

1. The first line of code imports the library package iostream.

2. Similar to the previous example, a method Horner is created with three parameters.

   int Horner(int a[], int n, int x)
   

3. A variable result is created and initialized with the array’s first element by dereferencing the pointer. The pointer *a is the same as writing arr[0].

   int result = *a;
   

   In the previous example, the method Horner needed a size component attached to its array: int result = a[n]; to point to the last element. Here, it is just dereferenced.

4. A for loop is created that iterates from 1 to n. In each iteration, the value of the result variable is updated with the value of the polynomial.

   The value of result is returned at the end of the method.

   for (int i = 1; i < n; i++) result = result * x + a[i];
   return result;
   

5. Inside the main function, an array is created with the value of coefficients. The polynomial used here is:

   $$
   p(x) = 5x^4 + 3x^3 - 2x^2 + 4x - 6; x=-2
   $$

   The array is created by taking the coefficients of the polynomials - int arr[] = {5,3,-2,4,-6};.

6. The variable n holds the degree of the polynomial. The value of n is computed by: n = size of array -1.

   int n = (*(&arr + 1) - arr) - 1;
   //  n =	  size of the array		    -   1;
   

7. The method Horner is called by passing the array, value of n, and value at x. The returned result is stored in a new integer variable and printed.

   int sol = Horner(arr, n, -2);
   std::cout << "Value of polynomial = " << sol;
   

Code:

#include <iostream>
int Horner(int a[], int n, int x) {
  int result = *a;
  for (int i = 1; i < n; i++) result = result * x + a[i];
  return result;
}

int main() {
  int arr[] = {5, 3, -2, 4, -6};
  int n = (*(&arr + 1) - arr) - 1;
  int sol = Horner(arr, n, -2);
  std::cout << "Value of polynomial = " << sol;
}

Output (Forward looping Horner’s rule in C++):

Value of polynomial = -20

Use Recursion to Find the Value of Polynomial Using Horner’s Rule in C++

So far, we have learned how to find the value of a polynomial using Horner’s rule in C++. It was done by iterating loops and updating the count using an accumulator variable.

In this example, the value of the polynomial is computed by recursion. Let’s look at the code.

1. The first line of code imports package iostream and defines namespace as std.

   #include <iostream>
   using namespace std;
   

2. A method Horner is created which has three parameters - a pointer integer *pi, another integer variable degree, which is the degree of the polynomial (used as n in the previous example), and x for passing value at x.

   int Horner(int* pi, int degree, int x)
   

3. The feature of the recursive function is to keep calling itself like a loop until a condition is met, which reduces the time complexity. For the condition, an if statement returns the value of pi at the 0th index only if the degree’s value has reduced to 0.

   if (degree == 0) {
     return pi[0];
   }
   

4. To apply recursion, the method Horner is called again instead of returning a value.

   return Horner(pi, degree - 1, x) * x + pi[degree];
   

   The above syntax keeps the Horner method to call itself repeatedly for the degree of the polynomial present. In an equation, the degree of the polynomial is its highest exponent.

   If the equation used in the last example is considered:

   $$ p(x) = 5x^4 + 3x^3 - 2x^2 + 4x - 6; x=-2 $$

   The degree of the polynomial is 4.

   This means the recursion will iterate itself for n+1 = 5 times (size of the array). At each iteration, the method will call itself until the degree’s value is reduced to 0.

   Once it reaches 0, the recursion will take the *p[0] element and pass it to its previous method call.

   return Horner(pi, degree - 1, x) * x + pi[degree];
   

   It is the same as opening an envelope inside an envelope until the last one is reached and then folded back again. The value at the last method call gets passed to its previous method call, and the computations are executed.

5. Inside the main function, an integer array is created to pass the coefficients of the equation to the method Horner. Then the value of the parameters is passed to the method.

   int sol = Horner(arr, 4, -2);
   

   The array is arr, degree - 4, and value at x, which is -2.

6. Lastly, the returned result is stored in an integer variable sol and gets printed.

Code:

#include <iostream>
using namespace std;

int Horner(int* pi, int degree, int x) {
  if (degree == 0) {
    return pi[0];
  }
  return Horner(pi, degree - 1, x) * x + pi[degree];
}
int main() {
  int arr[] = {5, 3, -2, 4, -6};
  int sol = Horner(arr, 4, -2);
  cout << "Value of Polynomial using recursion = " << sol;
}

Output:

Value of Polynomial using recursion = 34

Conclusion

This article explains how to find the value of polynomials using Horner’s rule in C++. The three methods have varying time complexities which can be a great learning tool for the reader.

It is recommended to try writing the codes yourself and then coming back to get hints. The reader will easily understand the concepts of finding the value of polynomials using Horner’s rule in C++.