# Fast evaluation of polynomials

Hello everybody !

I was reading a book on geometry which taught me that one could compute the volume of a simplex through the determinant of a matrix, and I thought (I'm becoming a worse computer scientist each day) that if the result is exact this may not be the computationally fastest way possible to do it.

Hence, the following problem : if you are given a polynomial in one (or many) variables $\alpha_1 x^1 + \dots + \alpha_n x^n$, what is the cheapest way (in terms of operations) to evaluate it ?

Indeed, if you know that your polynomial is $(x-1)^{1024}$, you can do much, much better than computing all the different powers of $x$ and multiply them by their corresponding factor.

However, this is not a problem of factorization, as knowing that the polynomial is equal to $(x-1)^{1024} + (x-2)^{1023}$ is also much better than the naive evaluation.

Of course, multiplication and addition all have different costs on a computer, but I would be quite glad to understand how to minimize the "total number of operations" (additions + multiplications) for a start ! I had no idea how to look for the corresponding litterature, and so I am asking for your help on this one :-)

Thank you !

Nathann

P.S. : I am actually looking for a way, given a polynomial, to obtain a sequence of addition/multiplication that would be optimal to evaluate it. This sequence would of course only work for THIS polynomial and no other. It may involve working for hours to find out the optimal sequence corresponding to this polynomial, so that it may be evaluated many times cheaply later on.

-
Perhaps polynomial chains are what you are looking for, see for example section 4.6.4 of The Art of Computer Programming. –  Pontus von Brömssen Jul 4 '11 at 19:46
If the target solution is to be optimized for software running on commodity hardware, it would be wise to expand your criteria a bit, as modern CPUs are typically dominated by instruction latency as opposed to throughput, meaning that the smallest possible number of adders and multipliers will not necessarily be the fastest. Further, if the the degree is high, you will become bound by memory latency as well. K-th order Horner's form tends to work well on x86, especially with K=2. This is a classic latency vs throughput trade-off balancing problem. –  Martin Källman Feb 2 at 22:33

If the polynomial is given as $\alpha_0x^0+\dots+\alpha_nx^n$ and you do not know a priori anything about the $\alpha_i$’s, then you can’t do better than Horner’s scheme (which takes $n$ additions and multiplications). If you know that the polynomial is sparse and you are given a list of nonzero coefficients, you can evaluate the individual terms using repeated squaring (this takes about $k$ additions and $O(k\log n)$ multiplications, where $k$ is the number of nonzero terms). Other information about the polynomial may also help in principle, such as some sort of symmetries in the coefficient list.

-
Oh ! I did not know this method's name, thank you ! :-) I was actually interested in the case in which you have full information on the polynomial. Is there any computation you could do on it that would let you find the minimum number of operations to evaluate this specific polynomial ? :-) –  Nathann Cohen Jul 4 '11 at 16:15
Nathann Cohen, what do you mean by 'full information'? –  quid Jul 4 '11 at 16:20
My question probably was not accurate enough, so I appended a comment at the end. I am not looking for an algorithm that would be able to evaluate a polynomial, but an algorithm which -- given a polynomial -- would output "the best algorithm possible to evaluate this polynomial", using the least number of additions/muliplications possible. It would know the exact coefficients of this polynomial and can spend as much time as it likes trying to find out the best sequence of addition/multiplications to evaluate it. This way, this polynomial can be evaluated very often afterwards at no cost ! :-) –  Nathann Cohen Jul 4 '11 at 16:23
You are basically asking about the arithmetical circuit complexity of the polynomial. For multivariate polynomials, this question leads to extremely hard problems in complexity, see en.wikipedia.org/wiki/Arithmetic_circuit_complexity for a start. Even in the univariate case, I doubt there is any general method to compute the complexity of specific polynomials. –  Emil Jeřábek Jul 4 '11 at 16:27
Nathann Cohen, thank you for the clarification. Not sure if I missed your p.s. to the question or it and my comment happened in parallel. –  quid Jul 4 '11 at 16:28

The simplest version of this question is: what is the quickest way to evaluate $x^n?$ For $n = 2^k,$ $k$ repeated squarings is obviously best, but for more complicated $n$ I believe that finding the optimum is very hard -- see Knuth, vol 2 for (much) more on these so-called "multiplication trees".

-

The cheapest way of finding the value of a polynomial, given unlimited preprocessing resources, is to look up the precalculated value in the table. However, if you know you are going to need several more values evaluated at successive intervals, you might try a method similar to that desired by Charles Babbage: differences. Namely, store the value and the the n kth order differences (similar to evaluations at derivatives) for point x, and then use n additions to derive the differences and value for the polynomial at the point x+1. If you need to loop through to evaluate the polynomial at successive integers, this gets those values with O(n) additions per evaluation point.

(Of course needing random or real access to the polynomial will require something different, but you might find storing values at derivatives useful for evaluating the polynomial at near by points, especially if multiplication is expensive..)

Gerhard "Email Me About System Design" Paseman, 2011.07.04

-
Regarding "the cheapest way": looking things up in a table comes with a cost, and the cost will generally be at least logarithmic in the table size –  Sasho Nikolov Oct 1 '13 at 16:19
Sasho, indeed it does. However, table-type access has been optimized at the compiler and machine levels, and I don't know of anything faster. Do you? Gerhard "Ask Me About System Design" Paseman, 2013.10.01 –  Gerhard Paseman Oct 1 '13 at 17:15
But that also seems to assume one knows at what points the polynomial needs to be evaluated and in general, once the number of possible points is big enough, an actual evaluation algorithm will be faster. While look up in small tables may be very fast, this is not at all the case for very large tables when random access actually becomes an unreasonable assumption. –  Sasho Nikolov Oct 1 '13 at 17:45
If we are worried about table size, we should also be worried about bit length. I suspect the claim (inferred from your comment) that for any polynomial P, there will be n_0 such that for all n >n_0 evaluating P(n) will be faster than looking up P(n) in a "Google-sized" table. (Here I mean tables accommodating 10^m values for m at most 40. m about 80 is likely physically impossible in this millenium.) Even with idealized infinite tables with extrapolated access times, I doubt the inference you suggest. Gerhard "Recall The Unlimited Preprocessing Power" Paseman, 2013.10.01 –  Gerhard Paseman Oct 1 '13 at 17:53
What I had in mind is the right computational model when one does dictionary look up in an enormous table. While the number of operations to do the look up will be proportional to bit size, such huge tables will be stored on disk. While an evaluation algorithm can be executed in main memory for any reasonable range, fetching data from disk will become the bottleneck. I am arguing that a simple single-memory-level RAM model is not appropriate to evaluate this. –  Sasho Nikolov Oct 2 '13 at 3:21

Consider the polynomial $f(x) = nx$, where $n$ is an integer. Here are two algorithms which will evaluate this polynomial:

Algorithm 1. Multiply $n$ by $x$.

Algorithm 2. Calculate $x + x + \ldots + x$.

Which is more efficient? Given fixed $n$, this depends on your processor architecture. And this is just about the simplest case imaginable -- we only have one variable, the polynomial is linear, and we're not even thinking about pipelined calculations yet. Also, as mentioned before, you are going to have to formalize the problem in some way which eliminates the "algorithm" consisting of a table giving the value at each machine-sized number. As stated, I don't think the question is answerable.

-

If you want to evaluate the polynomial at a lot of equidistant points, you can do "forward differencing"; here are 3 slides explaining the method: http://zach.in.tu-clausthal.de/teaching/info2_11/folien/evaluating%20a%20polynomial%20at%20equidistant%20points.pdf (they are in German, but I believe you'll still get it).

-
I also cite an answer involving differencing below. Can you say how forward differencing differs from kth order differences? Gerhard "Not Sure About Differing Differences" Paseman, 2011.07.14 –  Gerhard Paseman Jul 14 '11 at 17:31

For evaluation of a general polynomial in one variable, the provably fastest method is Horner's scheme as Emil has pointed out. It is worth mentioning that this scheme has a more popular face in the form of little Bézout's theorem paired with Synthetic division as is often taught in Precalculus courses in the U.S.A. This is implicitely present in the Wikipedia article for Horner's method, but the relationship is not well explained. A convenient consequence of this fact is that on computer algebra systems, storing polynomials in Horner normal form adds no performance benefit when it comes to evaluation.
To see that these two algorithms are the same one only needs to verify that the base step and the recursive procedure for both match. I do this for evaluation at $x_0$ of $$f(x)=\sum_{i=0}^n a_ix^i = \left((\dots(a_nx+a_{n-1})x+\dots)x+a_1\right)x+a_0,$$ where the center expression is the general form of a polynomial in one variable and the right-hand-side (RHS) is its Horner normal form. In synthetic division as in evaluation of the RHS following the order of operations, one begins by multipling $x_0\cdot a_n$ which will be denoted $y_n$. For the recursive step in synthetic division one sets $y_{i-1}=x_0\cdot y_i+a_{i}$ for $n>i\geq0$. For $i>0$, this is precisely the calculation of the $i^{th}$ set of parentheses counting out-to-in and thus can be thought of as the $(n-i)^{th}$ iteration of evaluating the RHS of the euqation.
In this example $f(x_0)=y_0$.

-