In mathematics and computer science, polynomial evaluation refers to computation of the value of a polynomial when its indeterminates are substituted for some values. In other words, evaluating the polynomial
at
consists of computing
See also Polynomial ring Β§Β Polynomial evaluation
For evaluating the univariate polynomial
the most naive method would use
multiplications to compute
, use
multiplications to compute
and so on for a total of
multiplications and
additions.Using better methods, such as Horner's rule, this can be reduced to
multiplications and
additions. If some preprocessing is allowed, even more savings are possible.