Horner's rule for polynomial evaluation: Difference between revisions
Content added Content deleted
(New task and Python solution.) |
(Add link) |
||
Line 16: | Line 16: | ||
'''Task Description''' |
'''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 [http://www.physics.utah.edu/~detar/lessons/c++/array/node1.html Horner's rule]. |
: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 [http://www.physics.utah.edu/~detar/lessons/c++/array/node1.html Horner's rule]. |
||
<br>C.f: [[Formal power series]] |
|||
=={{header|Python}}== |
=={{header|Python}}== |
Revision as of 03:30, 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
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) 200</lang>