Horner's rule for polynomial evaluation: Difference between revisions
(Added Scheme) |
(Tidy up the header material) |
||
Line 1: | Line 1: | ||
{{draft task}} |
{{draft task}} |
||
A fast scheme for evaluating a polynomial such as: |
A fast scheme for evaluating a polynomial such as: |
||
: <math>-19+7x-4x^2+6x^3\,</math> |
|||
when |
|||
⚫ | |||
: <math>x=3\;</math>. |
|||
⚫ | |||
⚫ | |||
<pre> |
|||
: <math>(((6) x - 4) x + 7) x - 19\;</math> |
|||
⚫ | |||
⚫ | |||
x = 3 |
|||
⚫ | |||
⚫ | |||
x ''':=''' 3 |
|||
accumulator = reversedcoeffs[0] |
|||
⚫ | |||
⚫ | |||
accumulator ''':=''' reversedcoeffs[0] |
|||
⚫ | |||
} |
|||
accumulator ''':=''' ( accumulator * x ) + reversedcoeffs[i] |
|||
'''done''' |
|||
''# accumulator now has the answer'' |
|||
'''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]. |
||
C.f: [[Formal power series]] |
|||
=={{header|Fortran}}== |
=={{header|Fortran}}== |
||
{{works with|Fortran|90 and later}} |
{{works with|Fortran|90 and later}} |
Revision as of 09:10, 31 March 2010
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 in this pseudocode:
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 in 1 to length(reversedcoffs) do accumulator := ( accumulator * x ) + reversedcoeffs[i] done # 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
Fortran
<lang fortran>program test_horner
implicit none
write (*, '(f5.1)') horner ((/-19.0, 7.0, -4.0, 6.0/), 3.0)
contains
function horner (coeffs, x) result (res)
implicit none real, dimension (:), intent (in) :: coeffs real, intent (in) :: x real :: res integer :: i
res = 0.0 do i = size (coeffs), 1, -1 res = res * x + coeffs (i) end do
end function horner
end program test_horner</lang> Output: <lang>128.0</lang>
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>
Scheme
<lang scheme>(define (horner lst x)
(define (*horner lst x acc) (if (null? lst) acc (*horner (cdr lst) x (+ (* acc x) (car lst))))) (*horner (reverse lst) x 0))
(display (horner (list -19 7 -4 6) 3)) (newline)</lang> Output: <lang>128</lang>