A fast scheme for evaluating a polynomial such as:

 



−
19
+
7
x
−
4

x

2


+
6

x

3





{\displaystyle -19+7x-4x^{2}+6x^{3}\,}


when

 



x
=
3



{\displaystyle x=3\;}

.
is to arrange the computation as follows:

 



(
(
(
(
0
)
x
+
6
)
x
+
(
−
4
)
)
x
+
7
)
x
+
(
−
19
)



{\displaystyle ((((0)x+6)x+(-4))x+7)x+(-19)\;}


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
accumulator := 0
for i in length(coefficients) downto 1 do
    # Assumes 1-based indexing for arrays
    accumulator := ( accumulator * x ) + coefficients[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.
Cf. Formal power series

begin
    % Horner's rule for polynominal evaluation                             %
    % returns the value of the polynominal defined by coefficients,        %
    %         at the point x. The number of coefficients must be in ub     %
    %         the coefficients should be in order with x^0 first, x^n last %
    real procedure Horner( real    array coefficients ( * )
                         ; integer value ub
                         ; real    value x
                         ) ;
    begin
        real xValue;
        xValue := 0;
        for i := ub step -1 until 1 do xValue := ( xValue * x ) + coefficients( i );
        xValue
    end Horner ;
    % task test case                                                       %
    begin
        real array coefficients ( 1 :: 4 );
        integer    cPos;
        cPos := 1;
        for i := -19, 7, -4, 6 do begin
            coefficients( cPos ) := i;
            cPos                 := cPos + 1
        end for_i ;
        write( r_format := "A", r_w := 8, r_d := 2, Horner( coefficients, 4, 3 ) )
    end test_cases
end.