Calculation of a polynomial value. Is everything trivial in this matter?

The calculation of the value of a polynomial at a point is one of the simplest classical programming problems.
When carrying out various kinds of calculations, it is often necessary to determine the values of polynomials for given values of the arguments. Often, the approximate calculation of functions comes down to the calculation of approximating polynomials.
The average reader Habrahabr can not be called inexperienced in the application of all kinds of perversions. Every second person will say that the polynomial must be calculated according to Horner's rule . But there is always a small “but,” is the Horner scheme always the most efficient?

I do not set the goal of accurately describing the algorithms for computing polynomials, but only to show that in some cases it is possible (necessary) to apply schemes with excellent Horner rules. For those who are interested in the material, at the end of the article is a list of literature, which can be found for a more detailed study of the issue.
In addition, sometimes it becomes insulting that the names of our Russian mathematicians remain little known. In addition, I am just pleased to talk about the work of our mathematicians.

Horner's scheme

In calculating the values of polynomials, Horner's rule has received widespread application. The method is named after the British mathematician William George Horner.
In accordance with this rule, an nth degree polynomial:

${{P} _ {n}} (x) = {{a} _ {0}} {{x} ^ {n}} + {{a} _ {1}} {{x} ^ {n-1 }} + ... + {{a} _ {n-1}} x + {{a} _ {n}}$

represented as

${{P} _ {n}} (x) = (... (({{a} _ {0}} x + {{a} _ {1}}) x + {{a} _ {2}}) x + ... + {{a} _ {n-1}}) x + {{a} _ {n}}.$

The calculation of the value of the polynomial is carried out in the order determined by the brackets. What do we have? To calculate a polynomial ${{P} _ {n}} (x)$ according to the Horner scheme, it is necessary to perform n multiplications and nk additions (here k is the number of polynomial coefficients equal to 0). If ${{a} _ {0}} = 1$ , then there will be n-1 multiplications.
It can be shown that to calculate polynomials of a general form, it is impossible to construct a scheme that is more economical in the number of operations than the Horner scheme.
The biggest attraction of Horner's scheme is the simplicity of the algorithm for calculating the value of the polynomial.

Exceptions

When calculating polynomials of a special kind, fewer operations may be required than when applying the universal Horner scheme. For example, calculating a degree ${{x} ^ {n}}$ according to Horner's scheme means sequentially multiplying n factors and requires n-1 multiplication. However, each first reader will say that to calculate, for example, ${{x} ^ {8}}$ need to sequentially calculate ${{x} ^ {2}} = x \ cdot x$ , ${{x} ^ {4}} = {{x} ^ {2}} \ cdot {{x} ^ {2}}$ , ${{x} ^ {8}} = {{x} ^ {4}} \ cdot {{x} ^ {4}}$ , i.e. complete only 3 multiplications instead of 7.

Is there anything else, after all, the Horner scheme is the most economical?

In fact, everything is decided by the amount of computation. If it is necessary to calculate one value of the polynomial, then nothing is better than Horner's scheme. But if the values of the polynomial are calculated at many points, then it becomes possible to save a large number of multiplication operations due to preliminary calculations performed exactly once. This can significantly speed up the program.

In some cases, it is advisable to use two-stage schemes to obtain polynomial values. At the first stage, actions are performed only on the coefficients of the polynomial; it is converted to a special form. At the second stage, the value of the polynomial itself is calculated for given values of the argument. In this case, it may turn out that the number of operations performed in the second stage will be less than in calculations according to the Horner scheme.

Again, I note that such calculation methods are useful in calculating polynomial values ${{P} _ {n}} (x)$ for a large number of x values. The gain is obtained due to the fact that the first stage for the polynomial is performed only once. An example is the calculation of elementary functions, where an approximating polynomial is prepared in advance.

In further considerations, speaking of the number of operations to calculate ${{P} _ {n}} (x)$ , I will keep in mind the complexity of the second stage of calculations.

J. Todt scheme for polynomials of degree 6

We have the following polynomial:

${{P} _ {6}} (x) = {{x} ^ {6}} + A {{x} ^ {5}} + B {{x} ^ {4}} + C {{x} ^ {3}} + D {{x} ^ {2}} + Ex + F.$

For calculations we use the following auxiliary polynomials:

${{p} _ {1}} (x) = x (x + {{b} _ {1}})$ ,

${{p} _ {2}} (x) = ({{p} _ {1}} + x + {{b} _ {2}}) ({{p} _ {1}} + {{b} _ {3}})$ ,

${{p} _ {3}} (x) = ({{p} _ {2}} + {{b} _ {4}}) ({{p} _ {1}} + {{b} _ {5}}) + {{b} _ {6}}$ .

The coefficients are ${{b} _ {j}}$ determined by the method of uncertain coefficients based on the condition ${{p} _ {3}} (x) \ equiv {{P} _ {6}} (x)$ . From the last condition, we compose a system of equations, equating the coefficients for equal degrees of polynomials.

The system itself, I will not give here. But it is easily solved by the method of substitutions, and one has to solve quadratic equations. The coefficients can be complex, but if the coefficients turn out to be valid, then the calculations require three multiplications and seven additions instead of five multiplications and six additions according to the Horner scheme.

There is no need to talk about the universality of this scheme, but the reader can visually evaluate the decrease in the number of operations in comparison with the Horner scheme.

Scheme Yu.L. Ketkova

Finally, I got to our mathematicians.

Yu.L. Ketkov gave a general idea of the nth degree polynomial for n> 5, always leading to real expressions and requiring the calculation of the nth degree polynomial to perform [(n + 1) / 2] + [n / 4] multiplications and n + 1 additions .

For example, for n = 2k, the Ketkov scheme reduces to finding polynomials:

${{N} _ {2}} (x) = x ({{b} _ {0}} + x),$

${{N} _ {4}} (x) = ({{N} _ {2}} + {{b} _ {1}} + x) ({{N} _ {2}} + {{b } _ {2}}) + {{b} _ {3}},$

${{N} _ {6}} (x) = {{N} _ {2}} {{N} _ {4}} + {{b} _ {4}} x + {{b} _ {5} },$

$\ cdots \ cdots \ cdots$

${{N} _ {2k}} (x) = ({{N} _ {2}} + {{s} _ {k}} {{b} _ {2k-2}}) {{N} _ {2k-2}} + {{r} _ {k}} {{b} _ {2k-2}} x + {{b} _ {2k-1}},$

where ${{r} _ {k}} = 0$ , ${{s} _ {k}} = 1$ for k - even, and ${{r} _ {k}} = 1$ , ${{s} _ {k}} = 0$ if k is odd (k> 2).

All unknown coefficients are found from equality ${{P} _ {n}} (x) = {{N} _ {2k}}$ . In the works of Ketkov, for solving the resulting systems, a method is given that always gives real coefficients ${{b} _ {j}}$ .

Schemes V.Ya. Pan

E. Belaga in his work gave rigorous proof of the impossibility of constructing a scheme for computing arbitrary polynomials of the nth degree, using in the second stage less than [(n + 1) / 2] +1 multiplications and n additions.

V.Ya. Pan dealt with optimal polynomial computation. In particular, he proposed several schemes for calculating real polynomials, which came very close to the estimates of E. Belagi. I will give some Pan schemes for real polynomials.
1. Scheme for computing polynomials of the fourth degree.
The polynomial is considered ${{P} _ {4}} (x) = {{a} _ {0}} {{x} ^ {4}} + {{a} _ {1}} {{x} ^ {3}} + {{a} _ {2}} {{x} ^ {2}} + {{a} _ {3}} x + {{a} _ {4}}$ .

Imagine ${{P} _ {4}} (x)$ in the form:

$g (x) = x (x + {{\ lambda} _ {1}}),$

${{P} _ {4}} (x) \ equiv {{a} _ {0}} \ left (\ left (g (x) + {{\ lambda} _ {2}} \ right) \ left ( g (x) + x + {{\ lambda} _ {3}} \ right) + {{\ lambda} _ {4}} right),$

Where

${{\ lambda} _ {1}} = \ frac {{{a} _ {1}} - {{a} _ {0}}} {2 {{a} _ {0}}}, {{\ lambda} _ {2}} = \ frac {{{a} _ {3}}} {{{a} _ {0}}} - {{\ lambda} _ {1}} \ frac {{{a} _ {2}}} {{{a} _ {0}}} + ({{\ \ lambda} _ {1}} + 1) \ lambda _ {1} ^ {2},$

${{\ lambda} _ {3}} = \ frac {{{a} _ {2}}} {{{a} _ {0}}} - {{\ lambda} _ {1}} ({{\ lambda} _ {1}} + 1) - {{\ lambda} _ {2}}, {{\ lambda} _ {4}} = \ frac {{{a} _ {4}}} {{{a } _ {0}}} - {{\ lambda} _ {2}} {{\ lambda} _ {3}}.$

2. The circuit for calculating ${{P} _ {n}} (x)$ , $n \ ge 5$ .
Building auxiliary polynomials $g (x)$ , $h (x)$ , ${{p} _ {s}} (x)$ :

$g (x) = x (x + {{\ lambda} _ {1}}), h (x) = g (x) + x, {{p} _ {0}} (x) = x,$

${{p} _ {s}} (x) = {{p} _ {s-1}} (x) \ left ((g (x) + {{\ lambda} _ {4s-2}}) ( h (x) + {{\ lambda} _ {4s-1}}) + {{\ lambda} _ {4s}} right) + {{\ lambda} _ {4s + 1}}$ , s = 1,2, ..., k.

To calculate the value of a polynomial expression using:

${{P} _ {n}} (x) \ equiv {{a} _ {0}} {{p} _ {k}} (x)$ at $n = 4k + 1$ ,

${{P} _ {n}} (x) \ equiv {{a} _ {0}} x {{p} _ {k}} (x) + {{\ lambda} _ {n}}$ at $n = 4k + 2$ ,

${{P} _ {n}} (x) \ equiv {{a} _ {0}} \ left ({{p} _ {k}} (x) (g (x) + {{\ lambda} _ {n-1}}) + {{\ lambda} _ {n}} \ right)$ at $n = 4k + 3$ ,

${{P} _ {n}} (x) \ equiv {{a} _ {0}} x \ left ({{p} _ {k}} (x) (g (x) + {{\ lambda} _ {n-2}}) + {{\ lambda} _ {n-1}} \ right) + {{\ lambda} _ {n}}$ at $n = 4k + 4$ ,

this scheme requires the second stage $[n / 2] +2$ of multiplication and $n + 1$ addition.

A feature of this scheme is that the coefficients ${{\ lambda} _ {j}}$ always exist for $n \ ge 5$ and the real coefficients of the original polynomial.

At V.Ya. There are other schemes for computing polynomials, including complex ones.

Conclusion

Summarizing the above, I note that the calculation of one or more values of the polynomial indisputably needs to be carried out using the Horner scheme.

However, if the number of polynomial values that need to be calculated is large, and the performance is very important, then it makes sense to consider the use of special methods for calculating polynomials.

Some readers will say that fiddling with schemes other than Horner’s is difficult, dreary and not worth messing with. However, in real life there are problems in which you just need to calculate a huge number of polynomial values with large degrees (for example, it can take months to calculate them), and halving the number of multiplications will give a significant gain in time, even if you have to spend a couple of days to implement a specific scheme for computing polynomials.

Literature

Ketkov Yu.L. About one method of computing polynomials on mathematical machines. // Proceedings of the universities. Radiophysics, t.1., No. 4, 1958
V. Ya. Pan, “Calculation of polynomials according to schemes with preliminary processing of coefficients and a program for automatically finding parameters”, J. Comput. mate. and mate. Fiz., 2: 1 (1962), 133–140
V. Ya. Pan, “On methods for calculating the values of polynomials”, UMN, 21: 1 (127) (1966), 103–134
V. Ya. Pan, “On the calculation of polynomials of the fifth and seventh degree with real coefficients”, J. Comput. mate. and mate. Fiz., 5: 1 (1965), 116–118
Pan V. Ya. Some schemes for calculating the values of polynomials with real coefficients. The problems of cybernetics. Vol. 5. M .: Nauka, 1961, 17–29.
Belaga E. G. On the calculation of the values of a polynomial in one variable with preliminary processing of the coefficients. The problems of cybernetics. Vol. 5. M .: Fizmatgiz, 1961, 7–15.

Tags: