Polynomial evaluation
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 formula_1 at formula_2 consists of computing formula_3 See also For evaluating the univariate polynomial formula_4 the most naive method would use formula_5 multiplications to compute formula_6, use formula_7 multiplications to compute formula_8 and so on for a total of formula_9 multiplications and formula_5 additions. Using better methods, such as Horner's rule, this can be reduced to formula_5 multiplications and formula_5 additions. If some preprocessing is allowed, even  more savings are possible. Background. This problem arises frequently in practice. In computational geometry, polynomials are used to compute function approximations using Taylor polynomials. In cryptography and hash tables, polynomials are used to compute k-independent hashing. In the former case, polynomials are evaluated using floating-point arithmetic, which is not exact. Thus different schemes for the evaluation will, in general, give slightly different answers. In the latter case, the polynomials are usually evaluated in a finite field, in which case the answers are always exact. General methods. Horner's rule. Horner's method evaluates a polynomial using repeated bracketing : formula_13 This method reduces the number of multiplications and additions to just formula_5 Horner's method is so common that a computer instruction "multiply–accumulate operation" has been added to many computer processors, which allow doing the addition and multiplication operations in one combined step. Multivariate. If the polynomial is multivariate, Horner's rule can be applied recursively over some ordering of the variables. E.g. can be written as An efficient version of this approach was described by Carnicer and Gasca. Evaluation with preprocessing. Arbitrary polynomials can be evaluated with fewer operations than Horner's rule requires if we first  preprocess the coefficients formula_17. An example was first given by Motzkin who noted that can be written as where the values formula_20 are computed in advance based on formula_21. Motzkin's method uses just 3 multiplications compared to Horner's 4. The values for each formula_22 can be easily computed by expanding formula_23 and equating the coefficients: Example. To compute the Taylor expansion formula_25, we can upscale by a factor 24, apply the above steps, and scale back down. That gives us the three multiplication computation Improving over the equivalent Horner form (that is formula_27) by 1 multiplication. Multipoint evaluation . Evaluate of a formula_5-degree polynomial formula_23 in multiple points formula_30 can be done with formula_31 multiplications by using Horner's method formula_32 times. Using above preprocessing approach, this can be reduced that by a factor of two, that is, to formula_33 multiplications. However, using the fast Fourier transform, it is possible to reduce the time requirement to just formula_34. In the case where the points in which we wish to evaluate the polynomials have some structure, simpler methods exists. For example, Knuth gives a method for tabulating polynomial values of the type Dynamic evaluation. In the case where formula_30  are not known in advance, Kedlaya and Umans gave a data structure for evaluating polynomials over a finite field of size formula_37 in time formula_38 per evaluation after some initial preprocessing. This was shown by Larsen to be essentially optimal. The idea is to transform formula_23 of degree formula_5 into a multivariate polynomial formula_41, such that formula_42 and the individual degrees of formula_43 is at most formula_44. Since this is over formula_45, the largest value formula_43 can take (over formula_47) is formula_48. Using the Chinese remainder theorem, it suffices to evaluate formula_43 modulo different primes formula_50 with a product at  least formula_51. Each prime can be taken to be roughly formula_52, and the number of primes needed, formula_53, is roughly the same. Doing this process recursively, we can get the primes as small as formula_54. That means we can compute and store formula_43 on all the possible values in formula_56 time and space. If we take formula_57, we get formula_58, so the time/space requirement is just formula_59 Kedlaya and Umans further show how to combine this preprocessing with fast (FFT) multipoint evaluation. This allows optimal algorithms for many important algebraic problems, such as polynomial modular composition. Specific polynomials. While  general polynomials require formula_60 operations to evaluate, some polynomials can be computed much faster. For example, the polynomial formula_61 can be computed using just one multiplication and one addition since formula_62 Evaluation of powers. A particularly interesting type of polynomial is powers like formula_63. Such polynomials can always be computed in formula_64 operations. Suppose, for example, that we need to compute formula_65; we could simply start with formula_66 and multiply by formula_66 to get formula_68. We can then multiply that by itself to get formula_69 and so on to get formula_70 and formula_65 in just four multiplications. Other powers like  formula_72 can similarly be computed efficiently by first computing formula_69 by 2 multiplications and then multiplying by formula_66. The most efficient way to compute a given power formula_63 is provided by addition-chain exponentiation. However, this requires designing a specific algorithm for each exponent, and the computation needed for designing these algorithms are difficult (NP-complete), so exponentiation by squaring is generally preferred for effective computations. Polynomial families. Often polynomials show up in a different form than the well known formula_76. For polynomials in Chebyshev form we can use Clenshaw algorithm. For polynomials in Bézier form we can use De  Casteljau's algorithm, and for B-splines there is De Boor's algorithm. Hard polynomials. The fact that some polynomials can be computed significantly faster than "general polynomials" suggests the question: Can we give an example of a simple polynomial that cannot be computed in time much smaller than its degree? Volker Strassen has shown that the polynomial cannot be evaluated by with less than formula_78 multiplications and formula_79 additions. At least this bound holds if only operations of those types are allowed, giving rise to a so-called "polynomial chain of length formula_80". The polynomial given by  Strassen has very large coefficients, but by probabilistic methods, one can show there must exist even polynomials with coefficients just 0's and 1's such that the evaluation requires at least formula_81 multiplications. For other simple polynomials, the complexity is unknown. The polynomial formula_82 is conjectured to not be computable in time formula_83 for any formula_84. This is supported by the fact, that if it can be computed fast then Integer factorization can be computed in polynomial time, breaking the RSA cryptosystem. Matrix polynomials. Sometimes the computational cost of scalar multiplications (like formula_85) is less than the computational cost  of "non scalar" multiplications (like formula_68). The typical example of this is matrices. If formula_51 is an formula_88 matrix, a scalar multiplication formula_89 takes about formula_90 arithmetic operations, while computing formula_91 takes about formula_92 (or formula_93 using fast matrix multiplication). Matrix polynomials are important for example for computing the Matrix Exponential. Paterson and Stockmeyer showed how to compute a degree formula_5 polynomial using only formula_95 non scalar multiplications and formula_96 scalar multiplications. Thus a matrix polynomial of degree can be evaluated in formula_97 time. If formula_98 this is less than formula_99 that is, faster than a single matrix multiplication with  the standard algorithm. This method works as follows: For a polynomial let be the least integer not smaller than formula_101 The powers formula_102 are computed with formula_103 matrix multiplications, and formula_104 are then computed by repeated multiplication by formula_105 Now, where formula_107 for . This requires just formula_103 more non-scalar multiplications. We can write this succinctly using the Kronecker product: