Horner's rule for polynomial evaluation: Difference between revisions
Content added Content deleted
(Added Java) |
(I meant the coeff of x^2 to be ''minus'' 4, not 4. Also made Python func version work with version 3.0) |
||
Line 5: | Line 5: | ||
<br>And compute the result from the innermost brackets outwards as: |
<br>And compute the result from the innermost brackets outwards as: |
||
<pre> |
<pre> |
||
coefficients = [-19, 7, 4, 6] # list coefficients of all x^0..x^n in order |
coefficients = [-19, 7, -4, 6] # list coefficients of all x^0..x^n in order |
||
x = 3 |
x = 3 |
||
reversedcoeffs = reverse(coefficients) |
reversedcoeffs = reverse(coefficients) |
||
Line 29: | Line 29: | ||
coeffs.add(-19.0); |
coeffs.add(-19.0); |
||
coeffs.add(7.0); |
coeffs.add(7.0); |
||
coeffs.add(4.0); |
coeffs.add(-4.0); |
||
coeffs.add(6.0); |
coeffs.add(6.0); |
||
System.out.println(polyEval(coeffs, 3)); |
System.out.println(polyEval(coeffs, 3)); |
||
Line 44: | Line 44: | ||
}</lang> |
}</lang> |
||
Output: |
Output: |
||
<pre> |
<pre>128.0</pre> |
||
=={{header|Python}}== |
=={{header|Python}}== |
||
<lang python>>>> def horner(coeffs, x): |
<lang python>>>> def horner(coeffs, x): |
||
Line 52: | Line 52: | ||
return acc |
return acc |
||
>>> horner( (-19, 7, 4, 6), 3) |
>>> horner( (-19, 7, -4, 6), 3) |
||
128</lang> |
|||
===Functional version=== |
===Functional version=== |
||
<lang python>>>> |
<lang python>>>> try: from functools import reduce |
||
except: pass |
|||
>>> def horner(coeffs, x): |
|||
return reduce(lambda acc, c: acc * x + c, reversed(coeffs)) |
return reduce(lambda acc, c: acc * x + c, reversed(coeffs)) |
||
>>> horner( (-19, 7, 4, 6), 3) |
>>> horner( (-19, 7, -4, 6), 3) |
||
128</lang> |
Revision as of 06:38, 31 March 2010
Horner's rule for polynomial evaluation is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
A fast scheme for evaluating a polynomial such as:
when
.
Is to arrange the computation as follows:
And compute the result from the innermost brackets outwards as:
coefficients = [-19, 7, -4, 6] # list coefficients of all x^0..x^n in order x = 3 reversedcoeffs = reverse(coefficients) accumulator = reversedcoeffs[0] for (i=1; i<length(reversedcoffs); i++){ accumulator = ( accumulator * x ) + reversedcoeffs[i] } # accumulator now has the answer
Task Description
- Create a routine that takes a list of coefficients of a polynomial in order of increasing powers of x; together with a value of x to compute its value at, and return the value of the polynomial at that value using Horner's rule.
C.f: Formal power series
Java
<lang java5>import java.util.ArrayList; import java.util.Collections; import java.util.List;
public class Horner {
public static void main(String[] args){ List<Double> coeffs = new ArrayList<Double>(); coeffs.add(-19.0); coeffs.add(7.0); coeffs.add(-4.0); coeffs.add(6.0); System.out.println(polyEval(coeffs, 3)); }
public static double polyEval(List<Double> coefficients, double x) { Collections.reverse(coefficients); Double accumulator = coefficients.get(0); for (int i = 1; i < coefficients.size(); i++) { accumulator = (accumulator * x) + (Double) coefficients.get(i); } return accumulator; }
}</lang> Output:
128.0
Python
<lang python>>>> def horner(coeffs, x): acc = coeffs[-1] for c in reversed(coeffs[:-1]): acc = acc * x + c return acc
>>> horner( (-19, 7, -4, 6), 3) 128</lang>
Functional version
<lang python>>>> try: from functools import reduce except: pass
>>> def horner(coeffs, x): return reduce(lambda acc, c: acc * x + c, reversed(coeffs))
>>> horner( (-19, 7, -4, 6), 3) 128</lang>