19
$\begingroup$

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.

$\endgroup$
2
  • 6
    $\begingroup$ Perhaps polynomial chains are what you are looking for, see for example section 4.6.4 of The Art of Computer Programming. $\endgroup$ Jul 4 '11 at 19:46
  • 2
    $\begingroup$ 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. $\endgroup$
    – awdz9nld
    Feb 2 '14 at 22:33
20
$\begingroup$

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.

$\endgroup$
9
  • 1
    $\begingroup$ Nathann Cohen, what do you mean by 'full information'? $\endgroup$
    – user9072
    Jul 4 '11 at 16:20
  • 3
    $\begingroup$ 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 ! :-) $\endgroup$ Jul 4 '11 at 16:23
  • 14
    $\begingroup$ 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. $\endgroup$ Jul 4 '11 at 16:27
  • 2
    $\begingroup$ In many cases you might need to evaluate the polynomial many times for the same coefficient, in which cases it can pay to compile it down to a more efficient scheme than Horner's method. Clearly an algorithm to do so exist: iterate through all polynomial circuits in order of complexity until one is found to be equivalent to the problem at hand. Whether this can be done efficiently is another story. $\endgroup$
    – Arthur B
    Jul 25 '16 at 21:23
  • 4
    $\begingroup$ You can actually improve upon Horner's scheme, reducing to n/2 multiplications. Knuth has a section on this in Volume 2, "4.6.4. Evaluation of Polynomials". $\endgroup$ Apr 23 '21 at 23:23
11
$\begingroup$

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".

$\endgroup$
5
$\begingroup$

EDIT: Looks like I overlooked that the OP stipulated he wants to minimize the total number of additions and multiplications. (Although he said he wanted to do that "to start," so arguably the below is still relevant.)

However, to address the question as stated, what you are essentially looking for is the https://en.wikipedia.org/wiki/Arithmetic_circuit_complexity


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.

$\endgroup$
2
  • $\begingroup$ The OP said that he is willing to neglect the differences between additions and multiplications, and treat them similarly. The question is answerable, and the answer is Horner's algorithm, look at the accepted answer. $\endgroup$
    – Alex M.
    Dec 19 '21 at 8:17
  • 1
    $\begingroup$ Okay, looks like I did miss that the OP is willing to consider multiplications the same as additions. However, Horner's method is not the correct answer either. For instance it would use 256 multiplications to evaluate x^256, which is very suboptimal. $\endgroup$ Dec 20 '21 at 14:58
4
$\begingroup$

If we are on an architecture which has multiple cores, CPU pipelines and multi-media extensions (MME) then Horner's method really doesn't have to be best.

If the polynomial is large, you can split into as many bins as you have processor cores. If you have two cores, for example $$f(x)=\sum_k\alpha_kx^k=x\left(\sum\alpha_{2k+1} (x^2)^k\right) + \sum\alpha_{2k}(x^2)^k$$ Each sum evaluated in a separate thread. Then of course you can apply any optimization by treating as a separate polynomial if you want.


Another idea is to precalculate $x,x^2,x^4,\cdots$ and store them in a table, then you can evaluate say $x^{43}$ with help of $43 = 32+8+2+1$, so you do $x \cdot x^2 \cdot x^8 \cdot x^{32}$ by grabbing those four numbers from the table. That's 4 multiplications instead of 43 - in general will be logarithmic. Worst case would be 2-logarithm rounded up number of multiplications. This can be useful as parallellized MME-instructions are common on modern CPUs.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
9
  • 1
    $\begingroup$ 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 $\endgroup$ Oct 1 '13 at 16:19
  • $\begingroup$ 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 $\endgroup$ Oct 1 '13 at 17:15
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 1 '13 at 17:45
  • $\begingroup$ 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 $\endgroup$ Oct 1 '13 at 17:53
  • 1
    $\begingroup$ Yes, and if I knew how to give a better answer to the question, then I would. If you know of a better way to get fast performance given unlimited preprocessing resources, please let us know. While table lookup may be theoretically unsatisfactory to you, it may turn out to be useful to the poster, especially if there is an access pattern to use in optimization. Gerhard "Willing To Agree To Disagree" Paseman, 2013.10.02 $\endgroup$ Oct 2 '13 at 19:00
1
$\begingroup$

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).

$\endgroup$
1
  • 1
    $\begingroup$ 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 $\endgroup$ Jul 14 '11 at 17:31
1
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

If I understood your question correctly, you are willing to do an arbitrarily large amount of precomputing on your polynomial in order to make the evaluation process at run time as fast as possible.

In other words, you want to find a some way of making your polynomial evaluation "sparse" in some sense.

My first intuition is that this is not possible for an arbitrary polynomial, i.e. the set of polynomials for which a "sparsification" is possible is a set of measure zero. Which is not to say it is not possible for certain specific polynomials.

In general, "sparseness" usually indicates some sort of underlying mathematical structure, which suggests you should attempt to understand said structure first.

Otherwise I believe the problem to be NP-complete for the general case. I will edit this answer with a proof if I can think of one.

$\endgroup$
5
  • 4
    $\begingroup$ The problem with your answer is that it states only vague, generic truths, and opinions. If you had read the other answers, you would have noticed that Horner's algorithm has been indicated as the fastest available algorithm (provably so), with an explicitly given computational complexity. "Sparseness", "NP-completeness"... these sound like buzzwords to me, in this context. This is a low-quality answer. $\endgroup$
    – Alex M.
    Dec 19 '21 at 8:13
  • 1
    $\begingroup$ There is so little information in the question. For example, if the $a_i$'s are small integers the polynomial may be made "sparse", in some computationally useful sense. But the coefficients may be high precision floats for all we know. $\endgroup$ Dec 19 '21 at 14:20
  • $\begingroup$ @Alex M. Not really. The majority of answers quote Horner's rule, but if you carefully read the question and the comments that is not the answer he was looking for. Yes, you can evaluate an arbitrary polynomial in exactly N additions and multiplications, but if you have, say a polynomial with many repeated roots like in the example provided in the question you can do better than Horner by just factoring the polynomial in advance and using exponentiation by squaring. $\endgroup$ Dec 20 '21 at 14:05
  • $\begingroup$ @Alex M. This suggests to me that you can systematically try every way of splitting the polynomial into sums of polynomials with enough repeated roots, something that could be in principle be tried using dynamic programming for polynomials with integer coefficients and would in general be a task with exponential complexity. $\endgroup$ Dec 20 '21 at 14:19
  • $\begingroup$ @Alex M. There are other possible factorizations too, for instance: x^3+4x^2+6x+4 = (((x+1)^2)^2 -1)/x saves operations in some sense. Of course division is usually significantly more expensive than multiplication, but there are analogous examples where the tradeoff makes sense. $\endgroup$ Dec 20 '21 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.