Calculating the value of a polynomial. Is everything trivial in this question?

Calculating the value of a polynomial at a point is one of the simplest classical programming problems.
When performing 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 is reduced to the calculation of approximating polynomials.
An ordinary reader Habrahabr can not be called inexperienced in the application of all sorts of perversions. Every second will say that the polynomial must be calculated according to Horner's rule . But there is always a small “but”, is Horner’s scheme always the most efficient?

I do not set a goal to accurately describe the algorithms for calculating polynomials, but only to show that in some cases it is possible (necessary) to apply the Horner's excellent rules. For those who are interested in the material, at the end of the article is a list of references, 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 obscure. Besides, it's just nice to talk about the work of our mathematicians.

Horner's Scheme

When calculating the values of polynomials, Horner's rule was widely applied. The method is named after the British mathematician William George Horner.
In accordance with this rule, the 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 polynomial value is performed in the order defined by the brackets. What do we have? To calculate the polynomial ${{P} _ {n}} (x)$ according to Horner’s scheme, n multiplications and nk additions must be performed (here k is the number of polynomial coefficients equal to 0). If a ${{a} _ {0}} = 1$ , then the multiplications will be n-1.
It can be shown that for calculating polynomials of a general form, one cannot construct a more economical scheme in terms of 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 a polynomial.

Exceptions

When calculating polynomials of a special type, a smaller number of operations may be required than when using the universal Horner scheme. For example, calculating the degree ${{x} ^ {n}}$ according to Horner's scheme, means the sequential multiplication of n factors and requires n-1 multiplication. However, every first reader will say that to calculate, for example, ${{x} ^ {8}}$ need to consistently calculate ${{x} ^ {2}} = x \ cdot x$ , ${{x} ^ {4}} = {{x} ^ {2}} \ cdot {{x} ^ {2}}$ , ${{x} ^ {8}} = {{x} ^ {4}} \ cdot {{x} ^ {4}}$ i.e. perform only 3 multiplications instead of 7.
')

Is there anything else, because Horner’s scheme is the most economical?

In fact, all solve the volume of calculations. If it is necessary to calculate one value of a polynomial, then nothing is invented better than the Horner scheme. But if the values of a polynomial are computed at many points, then it is 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, to obtain the values of polynomials, it is advisable to use two-stage schemes. At the first stage, only the coefficients of the polynomial are performed; it is converted to a special form. At the second stage, the value of the polynomial itself is calculated for the 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 computational methods are appropriate when calculating the values of a polynomial. ${{P} _ {n}} (x)$ for a large number of x values. The win is due to the fact that the first stage for the polynomial is performed only once. An example would be the calculation of elementary functions, where the approximating polynomial is prepared in advance.

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

J.Todt scheme for polynomials 6 degrees

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

Coefficients ${{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 with equal degrees of polynomials.

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

Talk about the universality of this scheme is not necessary, but the reader can clearly appreciate the reduction in the number of operations compared to the Horner scheme.

Scheme Yu.L. Ketkova

Finally, I got to our mathematicians.

Yu.L. Ketkov gave a general representation of the nth degree polynomial for n> 5, which always leads to real expressions and requires the nth degree of execution of [(n + 1) / 2] + [n / 4] multiplications and n + 1 additions to compute the polynomial .

For example, for n = 2k, the Ketkov scheme is reduced 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$ when k is even and ${{r} _ {k}} = 1$ , ${{s} _ {k}} = 0$ if k is odd (k> 2).

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

Schemes V.Ya. Pan

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

V.Ya. Ban dealt with optimal polynomial computation. In particular, they proposed several schemes for calculating real polynomials, which were very close to E. Belagi’s estimates. I will give some Pan schemes for real polynomials.
1. Scheme for calculating fourth degree polynomials.
Considered polynomial ${{P} _ {4}} (x) = {{a} _ {0}} {{x} ^ {4}} + {{a} _ {1}} {{x} ^ {3}} + {{a} _ {2}} {{x} ^ {2}} + {{a} _ {3}} x + {{a} _ {4}}$ .

Imagine ${{P} _ {4}} (x)$ as:

$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. Scheme for calculation ${{P} _ {n}} (x)$ , $n \ ge 5$ .
We build 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, use the expression:

${{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 in the second stage requires $[n / 2] +2$ multiplication and $n + 1$ addition.

The peculiarity of this scheme is that the coefficients ${{\ lambda} _ {j}}$ always exist at $n \ ge 5$ and the actual coefficients of the original polynomial.

W.Ya. There are other schemes for calculating polynomials, including complex ones.

Conclusion

Summarizing what has been said, I note that the calculation of one or more values of the polynomial must be undoubtedly carried out using the Horner scheme.

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

Some readers will say that it’s difficult to tinker with the use of schemes other than Horner’s, it’s dreary and you shouldn’t get involved with it. However, in real life there are tasks in which you just need to calculate a huge number of polynomial values with large degrees (for example, months can take them to calculate), and reducing the number of multiplications by half will give a significant time gain, even if you have to spend a couple of days on the implementation of a specific scheme for calculating polynomials.

Literature

Ketkov Yu.L. About one method of calculating polynomials on mathematical machines. // News of universities. Radio Physics, v.1., № 4, 1958
V. Ya. Pan, “Calculation of polynomials using schemes with preliminary processing of coefficients and a program for automatically finding parameters”, Zh. Vychisl. Math and mat. Phys., 2: 1 (1962), 133–140
V. Ya. Pan, “On methods of 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”, Zh. Vychisl. Math and mat. Phys. 5: 1 (1965), 116–118
Pan V. Ya. Some schemes for calculating the values of polynomials with real coefficients. Problems of cybernetics. Issue 5. M .: Nauka, 1961, 17–29.
Belaga .. G. On the calculation of the values of a polynomial of one variable with preliminary processing of coefficients. Problems of cybernetics. Issue 5. M .: Fizmatgiz, 1961, 7–15.

Source: https://habr.com/ru/post/279097/

All Articles