My Math Forum Fast polynomial evaluation

 Number Theory Number Theory Math Forum

 December 12th, 2017, 07:26 PM #1 Senior Member   Joined: Sep 2016 From: USA Posts: 520 Thanks: 293 Math Focus: Dynamical systems, analytic function theory, numerics Fast polynomial evaluation Short version: Consider a polynomial, $f: \mathbb{R}^d \to \mathbb{R}$ and suppose you are (and I am) interested in evaluation of $f(x)$ which utilizes a minimal number of multiplications. Is there an algorithm for determining the optimal manner in which to construct each monomial product? Here optimal means the minimum number of multiplications. Example: If $d=1$ and $f = \sum_{i=0}^n a_ix^i$, and every $a_i \neq 0$, then Horner's algorithm can be proved to satisfy the problem. In general, if $f$ is "dense" (most coefficients nonzero), Horner is expected to be optiimal or nearly optimal. Now, suppose $f$ is "sparse" meaning most coefficients are zero. Now it isn't clear how to proceed. Example: Let $f(x) = x^5 + x^{16}$. One particularly bad idea is to do the following: $x^5 = x*x*x*x*x \ (5 \text{ multiplications})$ $x^{16}= x^5*x*x*x*x*x*x*x*x*x*x*x \ (11 \text{ multiplications})$ A better idea would be the following which was generated by a (pseudo) greedy algorithm I implemented to try and solve this problem: $x^2 = x*x$ $x^3 = x^2*x$ $x^5 = x^2*x^3$ $x^{10} = x^5*x^5$ $x^{15} = x^{10}*x^5$ $x^{16} = x^{15}*x$ which requires only 6 multiplications. However, if you look closely you notice this is still not optimal. Consider $x^2 = x*x$ $x^4 = x^2*x^2$ $x^5 = x^4*x$ $x^8 = x^4*x^4$ $x^{16} = x^8*x^8$ which requires only 5 multiplications. The key here being (what the algorithm missed) that even though $x^5$ must be constructed at some point, it is still not the optimal path by which to obtain the $x^{16}$ term. Now, the question is, is there a known optimal solution to this problem? I'll settle for any problem isomorphic to this (I'm sure this is a graph theory problem in disguise) even if its slow. Additional Info (for those interested): The need here is motivated by 3 reasons: 1. My polynomials are not defined on $\mathbb{R}$, but rather in a Banach algebra, $X$, where multiplication is much much more expensive than addition. 2. My polynomials are not functions of 1 variable, but typically more like 10 variables. This makes brute forcing an optimal solution unlikely since a "typical" polynomial has an absurd number of terms and brute force algorithm would amount to traversing every possible tree of this size. 3. My polynomials are extremely sparse. This not only makes a brute force algorithm (even if it were possible) extremely non-elegant, but gives significant hope that there is a clever algorithm which doesn't need to exhaust every possible configuration. So anyone have some clever ideas?
 December 13th, 2017, 11:31 AM #2 Newbie   Joined: Nov 2017 From: US Posts: 5 Thanks: 4 Thinking out loud, one approach is to see how to use partition of a number to arrive at optimal set of computations. For example, partition of 5 is 7 (https://www.wolframalpha.com/input/?i=partition+of+5). 5 (Size =1) 4+1 (Size =2) 3+2 (Size =2) 3+1+1 (Size =3) 2+2+1 (Size =3) 2+1+1+1 (Size =4) 1+1+1+1+1 (Size =5) From here, if we push along these lines in recursive manner ,we may get an option for optimal solution. Thanks from SDK
December 13th, 2017, 11:45 AM   #3
Senior Member

Joined: Sep 2016
From: USA

Posts: 520
Thanks: 293

Math Focus: Dynamical systems, analytic function theory, numerics
Quote:
 Originally Posted by meditate Thinking out loud, one approach is to see how to use partition of a number to arrive at optimal set of computations. For example, partition of 5 is 7 (https://www.wolframalpha.com/input/?i=partition+of+5). 5 (Size =1) 4+1 (Size =2) 3+2 (Size =2) 3+1+1 (Size =3) 2+2+1 (Size =3) 2+1+1+1 (Size =4) 1+1+1+1+1 (Size =5) From here, if we push along these lines in recursive manner ,we may get an option for optimal solution.
You are of course correct. However, this is what is meant by the brute force solution. In order to find the minimal multiplications, one must exhaust all possible partitions up to the total degree of $f$ and then just count. This most definitely works, but it is computationally infeasible as the number of partitions blows up very fast even in only 1 dimension.

 December 13th, 2017, 01:11 PM #4 Member   Joined: Jan 2016 From: Athens, OH Posts: 92 Thanks: 47 I don't know if this helps, but a standard algorithm of order log(n) to evaluate $x^n$ will probably have many fewer multiplications than Horner's method applied to a (sparse) polynomial of degree n. This idea doesn't lead to an optimal solution, but it might be of practical use for your application. Thanks from Joppy and SDK
December 14th, 2017, 07:00 PM   #5
Senior Member

Joined: Sep 2016
From: USA

Posts: 520
Thanks: 293

Math Focus: Dynamical systems, analytic function theory, numerics
Quote:
 Originally Posted by johng40 I don't know if this helps, but a standard algorithm of order log(n) to evaluate $x^n$ will probably have many fewer multiplications than Horner's method applied to a (sparse) polynomial of degree n. This idea doesn't lead to an optimal solution, but it might be of practical use for your application.
What algorithm are you referring to? Whether or not it is useful depends how far from optimal it is. Obviously, I'm not using Horner's method here so the algorithm to beat is the greedy implementation I have now which is near optimal, and still not good enough in some cases.

I'm happy to obtain something which is still not optimal but improves on this. I'd appreciate some details if you have an idea.

 December 15th, 2017, 09:34 AM #6 Member   Joined: Jan 2016 From: Athens, OH Posts: 92 Thanks: 47 I was referring to the algorithm based on the binary representation of the positive integer n. The easiest implementation is recursive (c language), which has the same efficiency as a non-recursive version. Code:  double power(double x, int n) { double v; if (n == 1) { return (x); } v = power(x, n / 2); v *= v; if (n & 1) { // n is odd v *= x; } return (v); } It is obvious that the number of multiplications is at most $2\lfloor \log_2(n)\rfloor$. So I was thinking of polynomials of large degree n and just evaluate each term with a non-zero coefficient; an overestimate of the number of multiplications required for m non-zero coefficients is then $3m\lfloor \log_2(n)\rfloor$. For small n, this isn't going to help. Last edited by johng40; December 15th, 2017 at 10:28 AM. Reason: corrections
December 16th, 2017, 12:05 PM   #7
Senior Member

Joined: Sep 2016
From: USA

Posts: 520
Thanks: 293

Math Focus: Dynamical systems, analytic function theory, numerics
Quote:
 Originally Posted by johng40 I was referring to the algorithm based on the binary representation of the positive integer n. The easiest implementation is recursive (c language), which has the same efficiency as a non-recursive version. Code:  double power(double x, int n) { double v; if (n == 1) { return (x); } v = power(x, n / 2); v *= v; if (n & 1) { // n is odd v *= x; } return (v); } It is obvious that the number of multiplications is at most $2\lfloor \log_2(n)\rfloor$. So I was thinking of polynomials of large degree n and just evaluate each term with a non-zero coefficient; an overestimate of the number of multiplications required for m non-zero coefficients is then $3m\lfloor \log_2(n)\rfloor$. For small n, this isn't going to help.
My mistake, I misread your initial post and thought you were referring to asymptotic complexity of order $\log n$ where $n$ was the total degree of some sparse polynomial.

The computation for a single term is of course not a problem and already a greedy algorithm has this as a lower bound. Unfortunately, this is still pretty bad since applying it to every term of a sparse polynomial with total degree of $k$ terms you have something on the order of $\log(k!)$ multiplications.

In fact, this algorithm is in some sense what I need to do better than. Obviously, you can't do better for every polynomial since $f(x) = x^n$ would be among these competitors. In this case better here loosely means: If the polynomial admits an evaluation method which utilizes far fewer multiplications, then this method is utilized.

After poking around a bit on google/arxiv, I'm beginning to think that no such algorithm is known but I still hope this isn't the case.

 Tags evaluation, fast, polynomial

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Rejjy Calculus 11 December 25th, 2016 09:56 PM Hezekiah Elementary Math 7 October 19th, 2016 08:40 AM mathbalarka Calculus 5 February 18th, 2013 01:53 AM LionAM Calculus 2 August 18th, 2010 09:09 AM Soha Algebra 2 February 3rd, 2007 07:33 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top