horner {mvp}

Horner's method

Description

Horner's method for multivariate polynomials

Usage

horner(P,v)

Arguments

P

Multivariate polynomial

v

Numeric vector of coefficients

Details

Given a polynomial

p(x) = a_0 +a_1+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. But this is not implemented here because it's efficient. It is implemented because it works if x is itself a (multivariate) polynomial, and that is the second coolest thing ever. The coolest thing ever is the Reduce() function.

Author(s)

Robin K. S. Hankin

See Also

ooom

Examples

horner("x",1:5)
horner("x+y",1:3)

w <- as.mvp("x+y^2")
stopifnot(1 + 2*w + 3*w^2 == horner(w,1:3))  # note off-by-one issue

"x+y+x*y" %>% horner(1:3) %>% horner(1:2)