Horner's rule is a calculation method for reducing the number of polynomial multiplications, and is used to reduce program execution time.
Specifically, when considering the following polynomial as an example, the number of multiplications is usually 10.
The Horner's rule is to transform the formula as follows, and the number of multiplications can be reduced to 4 times.
＜Precautions for using the Horner's rule＞
In general, it is good if the execution time of the program is short, but it is not good to make it so that the original intention of the algorithm cannot be comprehended.
In that sense, the original form of the equation is slightly distorted in the Horner method, so I think it is better to leave an annotation in the program source.
＜Generalize and estimate the amount of computation＞
The number of multiplications in equation (1) can be represented by the sum of the arithmetic progression below, where n is the degree of the polynomial, and is proportional to the square of n.
On the other hand, the number of multiplications in equation (2) is equal to the degree of the polynomial, and the Horner's rule can significantly reduce the number of multiplications.
To express the amount of computation, we use the order notation as follows.
TOP MENU
