Horner's Method for polynomials
In the algebra courses, can you add a video covering Horner's method? It's easy to convert from standard form.
f(x)=3x^4+16x^3+7x^2+12x+15
This can be rewritten by adding some parenthesis and removing the exponents:
f(x)=((((3x+16)x+7)x+12)x+15
This requires the fewest adds and multiplies total, and is particularly efficient for computer math. It can be further simplified for equations with exponents of exponents, for example cosine is an even function and so can be approximated by a polynomial using only even coefficients, in the form:
f(x)=ax^6+bx^4+cx^2+d
Which by Horner's method would become:
f(x)=((ax^2+b)x^2+c)x^2+d
This requires one multiply to get x^2, which can then be used for each multiplication by x^2 without recalculating. That means you can do a cosine (and thus sine) approximation in 4 multiplies and 3 adds, whereas standard form requires 7 multiplies and 3 adds.
Considering how complex exponential curves are to calculate, polynomial approximations can become important optimizations. A polynomial fit can be identified with minimal error, to a high enough degree that the error is either negligible or of smaller magnitude than the precision used—in the latter case, the polynomial is exactly equivalent to the function it approximates. Minimizing the number of operations to compute a polynomial allows higher-degree, and thus lower-error, polynomial approximations.
This can be highly relevant in DSP and in custom hardware, or anywhere you have a fused multiply-add. Because of how computers handle multiplication—it's a tree of carry-save additions adding 3 numbers to produce 2—you often have a set of 2 terms that get incorporated further down, and so just sit on the data lines doing nothing. A fused multiply-add takes this opportunity to group those with some other term, add the three together, and produce 2 terms which are then used in the usual way, all without costing any more time because the multiplier had to wait for the other additions before it could use those 2 terms anyway. That can reduce Horner's method into a series of FMAs and effectively eliminate the additions, which are about half of the computation time.
Please sign in to leave a comment.