Transcript Efficient Computations and Horner’s Method

Efficient Computations
and
Horner’s Method
Evaluating Expressions Mathematics vs Computer Science
Mathematics makes no distinction between what a positive integral power means
and repeated multiplication. For example, in mathematics we see the following two
expressions as identical:
x3
and
x·x·x
There is a big difference when it come to applying this and have a machine do
this. One of the methods is actually preferred over the other in a computer
because it will increase both speed and accuracy.
Accuracy
Evaluating x·x·x is more accurate than x3 because the expression x·x·x is evaluated
using a hardware device (inside the ALU) that will exactly calculate the value if the
numbers stay within the machines precision (i.e. they number is not too big or too
small). This is not true in Mathematica, but is true in most compiled languages like
JAVA and C. The expression x3 is estimated using software. For most machine
computations this is ok (machine words have gotten long).
Speed
There are ways to code expressions
that cut down on the number of
computations that even need to be
done.
ALU
RAM Memory
Speed can be improved first by
keeping the processing in the ALU
instead of the memory which
performs slower. This is why
multiplication is preferred over
exponentiation.
Control
Unit
Disk Memory
CPU
Computer
Horner’s form of a polynomial
Any polynomial in the form a0+a1x+a2x2+…+anxn can be written
a0+x(a1+x(a2+x(…+anx))…)
In this form we will reduce the number of computations that need to be done.
Example: 5+7x+9x2+2x3 (Standard Form)
Horner’s Form:5+(7+(9+2·x)·x)·x
If you count the number of operation that are performed there are:
Standard form: 3 additions and 6 multiplications 7·x,9·x·x,2·x·x·x
Horner’s form: 3 additions and 3 multiplications
From this we see that Horner’s form for evaluating a polynomial is an improvement
over the standard way.
Horner’s Algorithm
Here is the algorithm for Horner’s form
get list of coefficients {a0,a1,a2,…,an}
express=0
For i=n,i0, i-1
express=ai+ x·express
Improvements in Horner's Algorithm
There are several ways to improve Horner's Algorithm when it comes to how
much multiplication needs to be done (i.e. how the powers are evaluated). A
binary approach can be used to limit the number of computations.
x  5
13
y1  x  5
y2  y1  y1
y4  y2  y2
y8  y4  y4
y13  y8  y4  y1
Evaluating this expression in this form requires:
13 additions
and
13 multiplications
Breaking the number 13 into its binary
representation we see we can dramatically cut
down on the number of computations required.
1 addition
and
5 multiplications
This gives a total of 6 computations compared to
the 26 that were required before. This uses only
about 23% of the computations that were
previously required.
Find the most efficient way to evaluate
the polynomial to the right.
Apply the standard Horner
Method first.
From this we see the only
powers of (x-7)that are
required are 1, 2 and 4.
4x  7  2x  7  3x  7  x  7
9
5
3
x  71  3x  72  2x  74  4x  78 
x  71  x  72  3  2x  72  4x  76 
x  71  x  72  3  x  72 2  4x  74 
y1  x  7
We rewrite the polynomial
using only the powers
required from the standard
Horner's Form.
y2  y1  y1
y4  y2  y2
y1 1  y2  3  y2 2  4 y4 