Horner's Method

Definition

Definition

Horner's Method is an algorithm used to efficiently evaluate polynomials. It reduces the number of arithmetic operations required compared to other methods by evaluating the polynomial as a nested multiplication and addition process

Explanation

evaluates a polynomial of the form $a_nx^n + a_{n-1}x^{n-1} + \ldots + a_1x + a_0$. Instead of evaluating each term individually and then summing them up, it uses a nested multiplication and addition approach. Starting from the highest degree term, it multiplies the current result by x and adds the next coefficient. This process continues until the constant term is reached.

Guidance

• Initialize a variable result to 0
• Iterate through the coefficients of the polynomial from highest degree to lowest
• For each coefficient
  • multiply the current result by x
  • add the coefficient to the result
• Once all coefficients are processed, the result will hold the value of the polynomial evaluated at x

Tips

• ensure the coefficients of the polynomial are stored efficiently to reduce memory usage
• implement bounds checking to handle cases where the polynomial has fewer terms than expected

Practice

Practice

evaluate_polynomial(coefficients, x):
  result = 0
  for i from n to 0:
    result = result * x + coefficients[i]
  return result

Solution

package main

func hornersMethod(coefficients []int, x int) int {
    result := coefficients[0]
    for i := 1; i < len(coefficients); i++ {
        result = result*x + coefficients[i]
    }
    return result
}

public class HornersMethod {

  public static int hornersMethod(int[] coefficients, int x) {
    int result = coefficients[0];
    for (int i = 1; i < coefficients.length; i++) {
      result = result * x + coefficients[i];
    }
    return result;
  }
}

function hornersMethod(coefficients, x) {
  let result = coefficients[0];
  for (let i = 1; i < coefficients.length; i++) {
    result = result * x + coefficients[i];
  }
  return result;
}

fun hornersMethod(coefficients: IntArray, x: Int): Int {
    var result = coefficients[0]
    for (i in 1 until coefficients.size) {
        result = result * x + coefficients[i]
    }
    return result
}

def horners_method(coefficients, x):
    result = coefficients[0]
    for coefficient in coefficients[1:]:
        result = result * x + coefficient
    return result

fn horners_method(coefficients: &[i32], x: i32) -> i32 {
    let mut result = coefficients[0];
    for &coefficient in &coefficients[1..] {
        result = result * x + coefficient;
    }
    result
}

function hornersMethod(coefficients: number[], x: number): number {
  let result = coefficients[0];
  for (let i = 1; i < coefficients.length; i++) {
    result = result * x + coefficients[i];
  }
  return result;
}