Horner's method — horner • freealg

Horner's method for multivariate polynomials

horner(P,v)

Arguments

P: Free algebra polynomial
v: Numeric vector of coefficients

Details

This function is (almost) the same as mvp::horner().

Given a polynomial

$$p(x) = a_0 +a_1x+a_2x^2+\cdots + a_nx^n$$

it is possible to express $p(x)$ in the algebraically equivalent form

$$p(x) = a_0 + x\left(a_1+x\left(a_2+\cdots + x\left(a_{n-1} +xa_n \right)\cdots\right)\right)$$

which is much more efficient for evaluation, as it requires only $n$ multiplications and $n$ additions, and this is optimal. Function horner() will take a freealg object for its first argument.

Author

Robin K. S. Hankin

Examples


horner("x",  1:4)  # note constant term is 1.
#> free algebra element algebraically equal to
#> + 1 + 2x + 3xx + 4xxx

horner("x+y",1:3) # note presence of xy and yx terms
#> free algebra element algebraically equal to
#> + 1 + 2x + 3xx + 3xy + 2y + 3yx + 3yy

horner("1+x+xyX",1:3)
#> free algebra element algebraically equal to
#> + 6 + 8x + 3xx + 3xxyX + 3xy + 8xyX + 3xyyX