霍纳法则（Horner's rule）

最新推荐文章于 2023-04-02 16:00:59 发布

winbobob

最新推荐文章于 2023-04-02 16:00:59 发布

阅读量2.5k

点赞数

分类专栏：学习笔记算法&数据结构文章标签： algorithm Horners rule

学习笔记同时被 2 个专栏收录

87 篇文章

订阅专栏

算法&数据结构

35 篇文章

订阅专栏

本文探讨了多项式高效评估的霍纳法则，通过优化计算过程减少浮点运算次数，尤其对于高次多项式更为显著。利用霍纳法则重新组织多项式的表达方式，从内到外逐层计算，大幅降低计算复杂度。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

http://blog.csdn.net/lwj1396/article/details/2669993

Horner's Rule for Polynomials

A general polynomial of degree

can be written as

$/begin{displaymath}P(x) = a_0 + a_1 x + a_2 x^2 + ... + a_n x^n = /sum_{i=0}^n a_i x^i/end{displaymath}$

(1)

If we use the Newton-Raphson method for finding roots of the polynomial we need to evaluate both

and its derivative

for any

It is often important to write efficient algorithms to complete a project in a timely manner. So let us try to design the algorithm for evaluating a polynomial so it takes the fewest flops (floating point operations, counting both additions and multiplications). For concreteness, consider the polynomial

$/begin{displaymath}7x^3 + 5x^2 - 4x + 2./end{displaymath}$

The most direct evaluation computes each monomial one by one. It takes multiplications for each monomial and additions, resulting in flops for a polynomial of degree .

That is, the example polynomial takes three flops for the first term, two for the second, one for the third, and three to add them together, for a total of nine.（n=3） If we reuse from monomial to monomial we can reduce the effort. In the above example, working backwards, we can save from the second term and get for the first in one multiplication by . This strategy reduces the work to flops overall or eight flops for the example polynomial. For short polynomials, the difference is trivial, but for high degree polynomials it is huge. A still more economical approach regroups and nests the terms as follows:

$/begin{displaymath}2 - 4x + 5x^2 + 7x^3 = 2 + x[-4 + x(5 + 7x)]./end{displaymath}$

(Check the identity by multiplying it out.) This procedure can be generalized to an arbitrary polynomial. Computation starts with the innermost parentheses using the coefficients of the highest degree monomials and works outward, each time multiplying the previous result by

and adding the coefficient of the monomial of the next lower degree. Now it takes